粉碎者¶
- 参考时间限制：2.5 秒（评测环境与性能）。
- 实际时限：在目标环境实测标准程序最慢测试文件的中位时间，乘以 2，再按 0.5 秒向上取整。
- 内存限制：256 MB。
背景故事¶
“Who wants to play?”
粉碎者起初被设计用于道路的清理，现在也被用于道路的清理。
地图是一棵树，每个节点都有一笔清理收益；有些地点入不敷出，收益便是负数。为了加快清理速度，粉碎者会开启涡轮增压。为了不浪费这份动力，一趟经过的道路不能少于 \(L\) 条；但燃料有限，也不能超过 \(R\) 条。
每个节点都可能发生必须立即清理的紧急情况。请分别计算：如果一趟行程必须经过这个节点，在道路数量满足要求的路径中，最多能获得多少总收益？
形式化问题描述¶
给定一棵有 \(n\) 个节点的无向树，节点编号为 \(1,\ldots,n\) ，节点 \(i\) 的权值为 \(v_i\) .
一次行程是一条不重复经过节点的简单路径，经过的边数在 \(L\) 到 \(R\) 之间，含上下界。收益是路径上所有节点的权值之和，包括两个端点，每个节点只计一次。允许从任意节点出发，也允许向任意方向行进。
对每个节点 \(i\) ，独立求所有经过 \(i\) 的合法路径的最大收益。当 \(L=0\) 时，只包含一个节点的路径也可以合法。
输入格式¶
第一行三个整数 \(n,L,R\) .
第二行 \(n\) 个整数 \(v_1,\ldots,v_n\) .
接下来 \(n-1\) 行，每行两个整数 \(u,v\) ，表示一条无向边。
输出格式¶
输出 \(n\) 行，第 \(i\) 行为节点 \(i\) 的答案。如果没有包含该节点的合法路径，输出 -1061109568 . 合法路径的收益可以为负数。
样例 1¶
输入¶
5 2 4
-338 971 -35 -221 458
1 2
3 1
3 4
2 5
输出¶
1091
1091
1056
835
1091
样例 2¶
输入¶
1 0 0
-7
输出¶
-7
样例 3¶
输入¶
4 3 3
2 -1 4 3
1 2
1 3
1 4
输出¶
-1061109568
-1061109568
-1061109568
-1061109568
样例解释¶
样例 1 中，路径 \(1\to2\to5\) 有两条边，收益为 \(1091\) ；路径 \(3\to1\to2\to5\) 有三条边，收益为 \(1056\) ；路径 \(4\to3\to1\to2\to5\) 有四条边，收益为 \(835\) .
实线高亮路径 \(3\to1\to2\to5\) ，虚线标出延伸到节点 \(4\) 的一段。树没有指定根，图中的上下位置不限制行进方向。
样例 2 的零边路径收益为 \(-7\) . 样例 3 的任意简单路径至多两条边，因而没有合法路径。
数据范围与保证¶
对 100% 的数据：\(1\le n\le300000\) ，\(0\le L\le R\le n-1\) ，\(-1000\le v_i\le1000\) ，\(1\le u,v\le n\) . 输入的边恰好构成一棵树。
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |