#6463. 「XXOI 2018」AK YOI

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: KingSann

题目描述

z2333 在 AK 了 UOI 之后,打算去 AK YOI。

但邪恶的 RQAQ 不打算让 z2333 AK YOI,因为这届 YOI 的题全部都是由 RQAQ 出的。

于是 RQAQ 用化学铁来让 z2333 丧失秒切题的能力。

但 z2333 发现自己只要花 1 分钟去切一道题后,他便能恢复秒切题的能力。

这个题的题目描述如下:


给定一棵树,同时给定一对 L,R ,对于每一个点,求出所有经过这个点,且边数在 [L,R] 的路径中,路径上点权和最大的那个点权和。

即对于每个点 u ,需要求出:

\Large f_u=\max \sum_{p \in (x,y)} v_p

其中满足:

  1. (x,y) 是一条经过 u 的简单路径;
  2. L \le |(x,y)| \le R

当然了,路径的端点也是要算上的。


如果你解决了这道题,z2333 会十分高兴,他会让 z6666 来传授给你如何玩玻璃球。

输入格式

第一行三个整数 n, L, R

第二行 n 个整数,表示 v_i

之后有 n - 1 行,每行两个整数 x, y 表示有一条连接着 x,y 的边。

输出格式

输出一行 n 个整数,分别表示 f_i

如果无解,输出 -3472328296227680305

样例

样例输入

5 1 3
-1 -6 7 7 4
1 2
2 3
3 4
4 5

样例输出

7 12 18 18 18

数据范围与提示

对于全部数据, 1 \le n,x_i,y_i \le 10^5,0 \le |v_i| \le 10^5,1 \le L \le R \le n