配点 : 100 点
問題文
帕肯王国的帕肯雪原里有一个洞穴。 有 N 个房间。另外,房间 i 具有初始大小 有 A_i 冰。 此外,洞内还有通道连接两个方向的房间。 N-1 书籍可用,i 主要通道是一个房间 u_i 和房间 v_i 是平局, 仅当c_i=1 仅当 i 热源放置在主通道中。现在,对于任何给定的房间,都可以保证通过某些通道可以到达所有其他房间。
時刻 0 从房间 i 单位时间冰仅在满足以下条件时: 它的大小以 1 的速度减小。然而冰的大小 不得小于 0 。 从
- 部屋 i 开始,尺寸为 0 你可以通过任一热源到达走廊,而无需穿过其他有较大冰块的房间。 您将收到
Q 问题,因此请逐一回答。i 第二个问题如下。
- 部屋 a_i 房间来自 考虑一条使前往 b_i 时所经过的路径数量最少的路线(可以证明这样的路线是唯一确定的)。此时,所有房间(房间 a_i, b_i 包括冰),时间 求 t_i 处冰尺寸的总和。
制約
- 2 \le N \le 200000
- 1 \le Q \le 200000
- 1 \le A_i \le 10^9
- 1 \le u_i, v_i \le N
- u_i \neq v_i
- c_i \in \{0, 1\}
- c_i = 1 变为 i 至少 1 有
- 1 \le a_i, b_i \le N
- 0 \le t_i \le 10^{10}
- 对于任何一个房间,通过一些通道都可以到达所有其他房间。
- 所有输入均为整数
小課題
- (7 点) N, Q \leq 1000,u_i = i, v_i = i+1\ (1 \le i \le N-1)
- (8 点) N, Q \leq 1000
- (7 点) u_i = i, v_i = i+1\ (1 \le i \le N-1),全部 关于 1 \le i, j \le Q 关于 t_i = t_j 。
- (14 点) u_i = i, v_i = i+1\ (1 \le i \le N-1),全部 关于 1 \le i \le Q , 当我输入 (a_i, b_i) = (1, N) 。
- (28 点) u_i = i, v_i = i+1\ (1 \le i \le N-1)
- (6 点) N, Q \leq 100000,全部 关于 1 \le i, j \le Q 关于 t_i = t_j 。
- (15 点) N, Q \leq 100000
- (15 点)没有额外的限制。
入力
输入是按以下格式从标准输入给出的。
N
A_1 A_2 \dots A_N
u_1 v_1 c_1
u_2 v_2 c_2
\vdots
u_{N-1} v_{N-1} c_{N-1}
Q
a_1 b_1 t_1
a_2 b_2 t_2
\vdots
a_Q b_Q t_Q
出力
Q 行。 i 行中,i 将问题的答案打印为整数。 截至
入力例 1
3 10 20 30 1 2 1 2 3 0 2 1 3 5 2 3 10
出力例 1
50 40
時刻 0 ,房间 1 和房间 2 可以到达有热源的通道(不穿过有其他冰的房间),冰就会开始融化。房间 3 是一个房间 冰尚未融化,因为 2 冰挡住了路线,无法到达热源。
- 1 第二个问题是时间 它涉及 5 的状态。房间 1 中冰的大小为 10 - 5 = 5、部屋 2 中冰的大小为 20 - 5 = 15 。房间 3 冰还没有开始融化,所以它的大小是 30 。您应该寻找的路线上的房间是 1, 2, 3 因此,它是总和 5 + 15 + 30 = 50 就是答案。
- 2 第二个问题是时间 它涉及 10 的状态。房间 1 冰已完全融化且尺寸减小。 0 变成一个房间 2 中冰的大小为 20 - 10 = 10 。您应该寻找的路线上的房间是 2, 3 因此,它是总和 10 + 30 = 40 就是答案。