#31 「 抉择 」

统计

喵星人正在玩一款战略游戏。

现在,他要去进攻敌国的n座城市,这些城市标号为1−n.

有一些城市之间有一条双向道路连接,保证任意两个城市之间都只有一条路径。

第i个城市有一个损失值$w_i$,当这个城市被摧毁,就会为喵星人带来$w_i$ 的贡献值。

喵星人的上司指示喵星人发起$m$次进攻:第$i$次进攻,由于不能引起太大的舆论风波,喵星人只能摧毁城市$u_i$到城市$v_i$ 路径上的城市. 同时,喵星人只能发射不超过$k_i$枚导弹,每一枚导弹只能摧毁路径上一段连续的城市。

并且任意两枚导弹不能摧毁一个相同的城市。 为了得到更高的得分,喵星人想让你告诉他每一次进攻最多能得到多少贡献值。

注意:如果不发射导弹可以取得更优的贡献值,那么可以不发射导弹。

由于喵星人其实只是看起来很厉害,因此每一次进攻之后所有受到影响的城市都会恢复原状,这意味着每一次进攻是独立的。

输入格式

第一行一个整数n,表示一共有n个城市。

接下来n − 1行,每行两个整数x, y,表示第x个城市与第y个城市之间有一条双向通道。

接下来一行n个整数,第i个整数表示$w_i$。

接下来一行一个整数q,表示有q次进攻。

接下来q行,每行三个整数$u_i$, $v_i$, $k_i$,与题目描述中意义一致.

输出格式

对于每一次进攻输出一行一个整数,表示这一次进攻的最大贡献值。

样例数据

input

5
1 2
2 3
3 4
4 5
5 3 -10 4 -5
1
5 1 2

output

12

数据规模与约定

$1 \le n \le 40000, 0 \le q \le 40000, k_i \ge 1$ , $\sum_{i=1}^q k_i \le 40000$。

$|w_i| \le 10^4$。

时间限制:1s

空间限制:512MB

Author: wyfcyx