优化网站推广教程排名,湖南省住房和城乡建设厅官方网站,宣传广告,威县做网站哪家好3妹#xff1a;2哥#xff0c;今日都立冬了#xff0c; 可是天气一点都不冷。 2哥 : 立冬了#xff0c;晚上要不要一起出去吃饺子#xff1f;#x1f95f; 3妹#xff1a;好呀好呀#xff0c;2哥请吃饺子喽 2哥 : 歪歪#xff0c;我说的是一起出去吃#xff0c;没说我…
3妹2哥今日都立冬了 可是天气一点都不冷。 2哥 : 立冬了晚上要不要一起出去吃饺子 3妹好呀好呀2哥请吃饺子喽 2哥 : 歪歪我说的是一起出去吃没说我请客好吧 3妹哼2哥真小气请吃顿饺子都不肯 2哥这样我们找一道算法题后做出来的要请吃饺子怎么样 3妹who 怕who, 来就来
题目
有一棵 n 个节点的无向树节点编号为 0 到 n - 1 根节点编号为 0 。给你一个长度为 n - 1 的二维整数数组 edges 表示这棵树其中 edges[i] [ai, bi] 表示树中节点 ai 和 bi 有一条边。
同时给你一个长度为 n 下标从 0 开始的整数数组 values 其中 values[i] 表示第 i 个节点的值。
一开始你的分数为 0 每次操作中你将执行
选择节点 i 。 将 values[i] 加入你的分数。 将 values[i] 变为 0 。 如果从根节点出发到任意叶子节点经过的路径上的节点值之和都不等于 0 那么我们称这棵树是 健康的 。
你可以对这棵树执行任意次操作但要求执行完所有操作以后树是 健康的 请你返回你可以获得的 最大分数 。
示例 1
输入edges [[0,1],[0,2],[0,3],[2,4],[4,5]], values [5,2,5,2,1,1] 输出11 解释我们可以选择节点 1 2 3 4 和 5 。根节点的值是非 0 的。所以从根出发到任意叶子节点路径上节点值之和都不为 0 。所以树是健康的。你的得分之和为 values[1] values[2] values[3] values[4] values[5] 11 。 11 是你对树执行任意次操作以后可以获得的最大得分之和。
示例 2
输入edges [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]], values [20,10,9,7,4,3,5] 输出40 解释我们选择节点 0 2 3 和 4 。
从 0 到 4 的节点值之和为 10 。从 0 到 3 的节点值之和为 10 。从 0 到 5 的节点值之和为 3 。从 0 到 6 的节点值之和为 5 。 所以树是健康的。你的得分之和为 values[0] values[2] values[3] values[4] 40 。 40 是你对树执行任意次操作以后可以获得的最大得分之和。
提示
2 n 2 * 10^4 edges.length n - 1 edges[i].length 2 0 ai, bi n values.length n 1 values[i] 10^9 输入保证 edges 构成一棵合法的树。
思路 dfs预处理出每个子树的元素和, 具体见代码中注释
java代码
class Solution {public long maximumScoreAfterOperations(int[][] edges, int[] values) {ListInteger[] g new ArrayList[values.length];Arrays.setAll(g, e - new ArrayList());g[0].add(-1); // 避免误把根节点当作叶子for (int[] e : edges) {int x e[0], y e[1];g[x].add(y);g[y].add(x);}// 先把所有分数加入答案long ans 0;for (int v : values) {ans v;}return ans - dfs(0, -1, g, values);}// dfs(x) 计算以 x 为根的子树是健康时失去的最小分数private long dfs(int x, int fa, ListInteger[] g, int[] values) {if (g[x].size() 1) { // x 是叶子return values[x];}long loss 0; // 第二种情况for (int y : g[x]) {if (y ! fa) {loss dfs(y, x, g, values); // 计算以 y 为根的子树是健康时失去的最小分数}}return Math.min(values[x], loss); // 两种情况取最小值}
}
