上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution {
public:
long long maxOutput(int n, vector<vector<int>>& edges, vector<int>& price) {
}
};
golang 解法, 执行用时: 244 ms, 内存消耗: 28.8 MB, 提交时间: 2023-01-17 15:34:54
func maxOutput(n int, edges [][]int, price []int) int64 {
ans := 0
g := make([][]int, n)
for _, e := range edges {
x, y := e[0], e[1]
g[x] = append(g[x], y)
g[y] = append(g[y], x) // 建树
}
// 返回带叶子的最大路径和，不带叶子的最大路径和
var dfs func(int, int) (int, int)
dfs = func(x, fa int) (int, int) {
p := price[x]
maxS1, maxS2 := p, 0
for _, y := range g[x] {
if y != fa {
s1, s2 := dfs(y, x)
// 前面最大带叶子的路径和 + 当前不带叶子的路径和
// 前面最大不带叶子的路径和 + 当前带叶子的路径和
ans = max(ans, max(maxS1+s2, maxS2+s1))
maxS1 = max(maxS1, s1+p)
maxS2 = max(maxS2, s2+p) // 这里加上 p 是因为 x 必然不是叶子
}
}
return maxS1, maxS2
}
dfs(0, -1)
return int64(ans)
}
func max(a, b int) int { if b > a { return b }; return a }
cpp 解法, 执行用时: 448 ms, 内存消耗: 155.3 MB, 提交时间: 2023-01-17 15:34:37
class Solution {
public:
long long maxOutput(int n, vector<vector<int>> &edges, vector<int> &price) {
vector<vector<int>> g(n);
for (auto &e : edges) {
int x = e[0], y = e[1];
g[x].push_back(y);
g[y].push_back(x); // 建树
}
long ans = 0;
// 返回带叶子的最大路径和，不带叶子的最大路径和
function<pair<long, long>(int, int)> dfs = [&](int x, int fa) -> pair<long, long> {
long p = price[x], max_s1 = p, max_s2 = 0;
for (int y : g[x])
if (y != fa) {
auto[s1, s2] = dfs(y, x);
// 前面最大带叶子的路径和 + 当前不带叶子的路径和
// 前面最大不带叶子的路径和 + 当前带叶子的路径和
ans = max(ans, max(max_s1 + s2, max_s2 + s1));
max_s1 = max(max_s1, s1 + p);
max_s2 = max(max_s2, s2 + p); // 这里加上 p 是因为 x 必然不是叶子
}
return {max_s1, max_s2};
};
dfs(0, -1);
return ans;
}
};
java 解法, 执行用时: 46 ms, 内存消耗: 82.9 MB, 提交时间: 2023-01-17 15:34:21
class Solution {
private List<Integer>[] g;
private int[] price;
private long ans;
public long maxOutput(int n, int[][] edges, int[] price) {
this.price = price;
g = new ArrayList[n];
Arrays.setAll(g, e -> new ArrayList<>());
for (var e : edges) {
int x = e[0], y = e[1];
g[x].add(y);
g[y].add(x); // 建树
}
dfs(0, -1);
return ans;
}
// 返回带叶子的最大路径和，不带叶子的最大路径和
private long[] dfs(int x, int fa) {
long p = price[x], maxS1 = p, maxS2 = 0;
for (var y : g[x])
if (y != fa) {
var res = dfs(y, x);
long s1 = res[0], s2 = res[1];
// 前面最大带叶子的路径和 + 当前不带叶子的路径和
// 前面最大不带叶子的路径和 + 当前带叶子的路径和
ans = Math.max(ans, Math.max(maxS1 + s2, maxS2 + s1));
maxS1 = Math.max(maxS1, s1 + p);
maxS2 = Math.max(maxS2, s2 + p); // 这里加上 p 是因为 x 必然不是叶子
}
return new long[]{maxS1, maxS2};
}
}
python3 解法, 执行用时: 524 ms, 内存消耗: 46.6 MB, 提交时间: 2023-01-17 15:34:05
# 树形dp
class Solution:
def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:
g = [[] for _ in range(n)]
for x, y in edges:
g[x].append(y)
g[y].append(x) # 建树
ans = 0
# 返回带叶子的最大路径和，不带叶子的最大路径和
def dfs(x: int, fa: int) -> (int, int):
nonlocal ans
max_s1 = p = price[x]
max_s2 = 0
for y in g[x]:
if y == fa: continue
s1, s2 = dfs(y, x)
# 前面最大带叶子的路径和 + 当前不带叶子的路径和
# 前面最大不带叶子的路径和 + 当前带叶子的路径和
ans = max(ans, max_s1 + s2, max_s2 + s1)
max_s1 = max(max_s1, s1 + p)
max_s2 = max(max_s2, s2 + p) # 这里加上 p 是因为 x 必然不是叶子
return max_s1, max_s2
dfs(0, -1)
return ans
