#6463. AK YOI

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

题目描述

z2333z2333z2333AKAKAKUOIUOIUOI 之后,打算去 AKAKAK YOIYOIYOI

但邪恶的 RQAQRQAQRQAQ 不打算让 z2333z2333z2333 AKAKAK YOIYOIYOI,因为这届 YOIYOIYOI 的题全部都是由 RQAQRQAQRQAQ 出的

于是 RQAQRQAQRQAQ化学铁来让 z2333z2333z2333 丧失秒切题的能力

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

这个题的题目描述如下


给定一棵树,同时给定一对 L,RL,RL,R

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

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

fu=max∑p∈(x,y)vp \huge 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

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


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

输入格式

第一行三个整数 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≤1051 \le n,x_i,y_i \le 10^51n,xi,yi105

0≤∣vi∣≤1050 \le |v_i| \le 10^50vi105

1≤L≤R≤n1 \le L \le R \le n1LRn