P17434 [LBA-OI R5 D] 星链光华

星络森林里，每棵树上都住着发光的星灵。他们相信最美的形态是“星链花”。

给定一棵 $n$ 个点的无根树，点 $v$ 有非负权值 $w_v$，表示星灵的光芒。一次询问给出 $u,k$。 树灵要选出一个包含 $u$ 的连通点集 $S$，满足： - 任意 $v\in S$ 到 $u$ 的树上距离不超过 $k$； - 从 $u$ 伸出的每条分支都是一条笔直的链，不能分岔。也就是说，在 $S$ 中，除 $u$ 外每个点最多与 $S$ 中另外两个点相邻。 一个点集的权值是其中所有点的权值之和。对每次询问，求满足条件的点集中权值最大是多少。 其中树上距离指两点最短路径经过的边数。

第一行两个整数 $n, m$。 第二行 $n$ 个非负整数 $w_1, w_2, \dots, w_n$，表示点权。 接下来 $n-1$ 行，每行两个整数 $u,v$，表示树上存在一条边 $(u,v)$。 接下来 $m$ 行，每行两个整数 $u, k$，表示一次询问。

输出 $m$ 行，每行一个整数表示该次询问的答案。

**本题目采用子任务捆绑测试。** 对于 $100\%$ 的数据：$k,n,m \le 2\times 10^5$，$0\le w_i\le 10^9$。 ::cute-table{tuack} | 子任务 | 分值 | 数据范围 | 特殊性质 | | :---: | :---: | :---: | :---: | | 1 | 10 | $n, m \le 300$ | 无 | | 2 | 15 | $n, m \le 5000$ | ^ | | 3 | 15 | 无特殊限制 | $k\le100$ | | 4 | 20 | ^ | $u=1$ | | 5 | 40 | ^ | 无 |