背景

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

题目描述

给定一棵 $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$ 行，每行一个整数表示该次询问的答案。

7 7
9 8 9 5 2 4 4 
1 2
1 3
2 4
3 5
5 6
1 7
2 4
5 2
3 4
5 1
5 2
4 4
7 1

37
24
37
15
24
33
13

提示

本题目采用子任务捆绑测试。

对于 $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 | ^ | 无 |