#P18732. [正睿NOI2021训练] -2
[正睿NOI2021训练] -2
-2
有一棵 个节点的树,第 个节点的权值为 ,初始时所有节点都是白色。
好吃选择一个起点 ,随后好吃和邓老师轮流操作,好吃先操作。
- 好吃每次可以停留在当前节点,或移动到一个相邻的白色节点。停留不要求当前节点是白色。
- 邓老师每次选择一个白色节点,将其染黑。
当所有节点都被染黑时,游戏立即结束。若好吃最后位于节点 ,则好吃得到 分,邓老师得到 分。双方都希望自己的得分最大。
对于每个起点 ,求双方采用最优策略时好吃的最终得分。
输入格式
第一行一个正整数 ;第二行 个正整数 。
接下来 行,每行两个整数 ,表示树的一条无向边。
输出格式
输出一行 个整数,第 个表示以节点 为起点时的答案。
数据范围
,,。保证输入是一棵树。
样例 1
输入
10
8 9 7 4 5 9 6 2 6 7
3 7
7 8
3 10
9 3
5 3
3 1
8 4
5 2
5 6
输出
8 9 9 4 9 9 8 6 8 8