# 粉碎者

- 参考时间限制：**2.5 秒**（[评测环境与性能](../../../docs/评测环境与性能.md)）。
- 实际时限：在目标环境实测标准程序最慢测试文件的中位时间，乘以 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

### 输入

```text
5 2 4
-338 971 -35 -221 458
1 2
3 1
3 4
2 5
```

### 输出

```text
1091
1091
1056
835
1091
```

## 样例 2

### 输入

```text
1 0 0
-7
```

### 输出

```text
-7
```

## 样例 3

### 输入

```text
4 3 3
2 -1 4 3
1 2
1 3
1 4
```

### 输出

```text
-1061109568
-1061109568
-1061109568
-1061109568
```

## 样例解释

样例 1 中，路径 $1\to2\to5$ 有两条边，收益为 $1091$ ；路径 $3\to1\to2\to5$ 有三条边，收益为 $1056$ ；路径 $4\to3\to1\to2\to5$ 有四条边，收益为 $835$ .

![经过节点 3 的最优路径以及经过节点 4 的最优路径](assets/cleanup-paths.svg)

实线高亮路径 $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% | 无额外条件 |