← 返回题目列表

AtCoder · pakencamp_2025_day2_d

D. 冰融化

中文机器翻译题面 查看原题

配点 : 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}
  • 对于任何一个房间,通过一些通道都可以到达所有其他房间。
  • 所有输入均为整数

小課題

  1. (7 点) N, Q \leq 1000,u_i = i, v_i = i+1\ (1 \le i \le N-1)
  2. (8 点) N, Q \leq 1000
  3. (7 点) u_i = i, v_i = i+1\ (1 \le i \le N-1),全部 关于 1 \le i, j \le Q 关于 t_i = t_j 。
  4. (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) 。
  5. (28 点) u_i = i, v_i = i+1\ (1 \le i \le N-1)
  6. (6 点) N, Q \leq 100000,全部 关于 1 \le i, j \le Q 关于 t_i = t_j 。
  7. (15 点) N, Q \leq 100000
  8. (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 就是答案。