#6463. AK YOI

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

题目描述

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

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

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

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

这个题的题目描述如下:


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

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

fu=max⁡∑p∈(x,y)vp \Large f_u=\max \sum_{p \in (x,y)} v_p fu=maxp(x,y)vp

其中满足:

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

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


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

输入格式

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

第二行 nnn 个整数,表示 viv_ivi

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

输出格式

输出一行 nnn 个整数,分别表示 fif_ifi

如果无解,输出 −3472328296227680305-34723282962276803053472328296227680305

样例

样例输入

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

样例输出

7 12 18 18 18

数据范围与提示

对于全部数据,1≤n,xi,yi≤105,0≤∣vi∣≤105,1≤L≤R≤n1 \le n,x_i,y_i \le 10^5,0 \le |v_i| \le 10^5,1 \le L \le R \le n1n,xi,yi105,0vi105,1LRn