A6289 | 最大颜色子树
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
给定一棵包含 $n$ 个顶点的树。树是一个包含 $n-1$ 条边的连通无向图。树上的每个顶点 $v$ 都被赋予了一种颜色（如果顶点 $v$ 是白色，则 $a_v = 1$，如果顶点 $v$ 是黑色，则 $a_v = 0$）。
你需要对于每个顶点 $v$，解决如下问题：在所有包含顶点 $v$ 的子树中，白色顶点数与黑色顶点数的最大差值是多少？
树的子树是原树的一个连通子图。更正式地说，如果你选择的子树包含 $cnt_w$ 个白色顶点和 $cnt_b$ 个黑色顶点，你需要最大化 $cnt_w - cnt_b$。
你需要对于每个顶点 $v$，解决如下问题：在所有包含顶点 $v$ 的子树中，白色顶点数与黑色顶点数的最大差值是多少？
树的子树是原树的一个连通子图。更正式地说，如果你选择的子树包含 $cnt_w$ 个白色顶点和 $cnt_b$ 个黑色顶点，你需要最大化 $cnt_w - cnt_b$。
输入格式
第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示树的顶点数。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 1$），其中 $a_i$ 表示第 $i$ 个顶点的颜色。
接下来 $n-1$ 行，每行描述一条树的边。第 $i$ 条边由两个整数 $u_i$ 和 $v_i$ 表示，表示该边连接顶点 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n, u_i \ne v_i$）。
保证给定的边构成一棵树。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le 1$），其中 $a_i$ 表示第 $i$ 个顶点的颜色。
接下来 $n-1$ 行，每行描述一条树的边。第 $i$ 条边由两个整数 $u_i$ 和 $v_i$ 表示，表示该边连接顶点 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n, u_i \ne v_i$）。
保证给定的边构成一棵树。
输出格式
输出 $n$ 个整数 $res_1, res_2, \dots, res_n$，其中 $res_i$ 表示在所有包含顶点 $i$ 的子树中，白色顶点数与黑色顶点数的最大差值。
输入输出样例
输入 #1
9 0 1 1 1 0 0 0 0 1 1 2 1 3 3 4 3 5 2 6 4 7 6 8 5 9
输出 #1
2 2 2 2 2 1 1 0 2
输入 #2
4 0 0 1 0 1 2 1 3 1 4
输出 #2
0 -1 1 -1
## 样例解释
### 样例 #1
颜色：白点记为 +1，黑点记为 −1：
- 1:−1, 2:+1, 3:+1, 4:+1, 5:−1, 6:−1, 7:−1, 8:−1, 9:+1
对每个点，找一棵「包含该点的连通子树」，使得这些点的权值和最大：
- 点 1：例如选子树 {1,2,3,4}，和 = −1+1+1+1 = 2，不能更大，所以 res₁ = 2；
- 点 3：例如选 {3,4}，和 = 1+1 = 2，所以 res₃ = 2；
- 点 5：例如选 {3,4,5,9}，和 = 1+1−1+1 = 2，所以 res₅ = 2；
- 点 6：例如选 {1,2,3,4,6}，和 = −1+1+1+1−1 = 1，所以 res₆ = 1；
- 点 8：最多选到和 = 0（如 {1,2,3,4,6,8}），所以 res₈ = 0。
其余点也可类似枚举，最终得到输出：
---
### 样例 #2
颜色转权值：
- 1:−1, 2:−1, 3:+1, 4:−1
- 点 3：选 {3}，和 = 1，为最大，res₃ = 1；
- 点 2：选 {2}，和 = −1，比包含 1 的任何更大子树都好，res₂ = −1；
- 点 4：同理，res₄ = −1；
- 点 1：选 {1,3}，和 = −1+1 = 0，为最大，res₁ = 0。
所以输出为：
### 样例 #1
颜色：白点记为 +1，黑点记为 −1：
- 1:−1, 2:+1, 3:+1, 4:+1, 5:−1, 6:−1, 7:−1, 8:−1, 9:+1
对每个点，找一棵「包含该点的连通子树」，使得这些点的权值和最大：
- 点 1：例如选子树 {1,2,3,4}，和 = −1+1+1+1 = 2，不能更大，所以 res₁ = 2；
- 点 3：例如选 {3,4}，和 = 1+1 = 2，所以 res₃ = 2；
- 点 5：例如选 {3,4,5,9}，和 = 1+1−1+1 = 2，所以 res₅ = 2；
- 点 6：例如选 {1,2,3,4,6}，和 = −1+1+1+1−1 = 1，所以 res₆ = 1；
- 点 8：最多选到和 = 0（如 {1,2,3,4,6,8}），所以 res₈ = 0。
其余点也可类似枚举，最终得到输出：
2 2 2 2 2 1 1 0 2。---
### 样例 #2
颜色转权值：
- 1:−1, 2:−1, 3:+1, 4:−1
- 点 3：选 {3}，和 = 1，为最大，res₃ = 1；
- 点 2：选 {2}，和 = −1，比包含 1 的任何更大子树都好，res₂ = −1；
- 点 4：同理，res₄ = −1；
- 点 1：选 {1,3}，和 = −1+1 = 0，为最大，res₁ = 0。
所以输出为：
0 -1 1 -1。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？