匈牙利是一个拥有 $N$ 个城市的国家，城市编号从 $0$ 到 $N - 1$。
这些城市由 $N - 1$ 条双向道路连接，道路编号从 $0$ 到 $N - 2$。道路 $j$ ($0 \le j \le N - 2$) 连接城市 $U[j]$ 和城市 $V[j]$，长度为 $T[j]$，也就是说，在两城市之间通行需要花费 $T[j]$ 个单位的时间。每条道路连接两个不同的城市，且任意两个城市之间最多只有一条道路连接。
两个不同城市 $a$ 和 $b$ 之间的路径是指一个由互不相同的城市组成的序列 $p_0, p_1, \dots, p_l$，满足：
- $p_0 = a$，
- $p_l = b$，
- 对于每个 $i$ ($0 \le i < l$)，都有一条道路连接城市 $p_i$ 和 $p_{i+1}$。
可以通过这些道路从任意城市前往其他任意城市，也就是说，任意两个不同的城市之间都存在一条路径。请注意，连接任意一对城市的路径是唯一的。
城市 $a$ 和 $b$ 之间的距离记为 $d(a, b)$，定义如下：
- 如果 $a = b$，则 $d(a, b) = 0$，
- 否则，$d(a, b)$ 为连接 $a$ 和 $b$ 之间路径上相邻城市的道路总长度。
Karcsi 是一名卡车司机，他需要在各个城市完成一定数量的货物送达任务。对于每个 $i$ ($0 \le i \le N - 1$)，Karcsi 需要在城市 $i$ 完成 $W[i]$ 次送达。Karcsi 从城市 $0$ 出发，他可以按任意顺序完成送达，最后返回城市 $0$。一个送达方案是一个（可能为空的）城市序列 $c_1, c_2, \dots, c_m$，满足对于每个 $i$ ($0 \le i < N$)，该序列中恰好包含城市 $i$ 共 $W[i]$ 次。
一个方案 $c_1, c_2, \dots, c_m$ 的送达时间是序列 $0, c_1, c_2, \dots, c_m, 0$ 中相邻城市之间距离的总和，即 $d(0, c_1) + d(c_1, c_2) + \dots + d(c_m, 0)$。
Karcsi 需要工作 $Q$ 天。在每天开始时，其中一个城市所需的送达次数会发生变化。对于某个城市 $S$ 和非负整数 $X$，$W[S]$ 的值变为 $X$。只要在之后的某天开始时没有被再次修改，$W[S]$ 的值就保持为 $X$。
Karcsi 按小时计薪。他希望选择一个送达方案，使得送达时间在所有可能的方案中达到最大。你的任务是计算 Karcsi 工作的每一天所能达到的最大送达时间。
实现细节
你需要实现以下两个函数：
void init(int N, int[] U, int[] V, int[] T, int[] W)N：城市的数量。U,V：长度为 $N - 1$ 的数组，描述道路连接情况。T：长度为 $N - 1$ 的数组，描述道路长度。W：长度为 $N$ 的数组，描述每个城市的初始送达次数。- 对于每个测试用例，该函数在调用
max_time之前恰好被调用一次。
int64 max_time(int S, int X)S,X：描述送达次数变化的整数。$W[S]$ 的值应被设置为 $X$。- 该函数应首先执行指定的更新，然后返回所有可能送达方案中的最大送达时间。
- 该函数恰好被调用 $Q$ 次。
样例
考虑以下调用序列：
init(5, [0, 0, 1, 1], [1, 2, 3, 4], [1, 2, 3, 1], [0, 0, 1, 0, 1])这些参数对应于下图所示的道路网络。红色数字表示每个城市的初始送达次数。
max_time(0, 1)更新后，我们有 $W = [1, 0, 1, 0, 1]$。一个可能的送达方案是序列 $4, 2, 0$。在这种情况下，Karcsi 依次访问城市 $0, 4, 2, 0, 0$，送达时间为 $d(0, 4) + d(4, 2) + d(2, 0) + d(0, 0) = 2 + 4 + 2 + 0 = 8$。
不存在送达时间大于 8 的送达方案，因此该函数应返回 8。
下表总结了对 max_time 的更多调用示例：
| 调用 | 更新后的 $W$ | 最优方案 | 最大送达时间 |
|---|---|---|---|
max_time(3, 3) |
[1, 0, 1, 3, 1] |
3, 0, 3, 2, 3, 4 |
$4 + 4 + 4 + 6 + 6 + 4 + 2 = 30$ |
max_time(0, 0) |
[0, 0, 1, 3, 1] |
3, 2, 3, 4, 3 |
$4 + 6 + 6 + 4 + 4 + 4 = 28$ |
max_time(4, 0) |
[0, 0, 1, 3, 0] |
3, 2, 3, 3 |
$4 + 6 + 6 + 0 + 4 = 20$ |
max_time(2, 0) |
[0, 0, 0, 3, 0] |
3, 3, 3 |
$4 + 0 + 0 + 4 = 8$ |
max_time(3, 0) |
[0, 0, 0, 0, 0] |
空 | $0$ |
数据范围
- $2 \le N \le 100\,000$
- 对于满足 $0 \le j \le N - 2$ 的每个 $j$，有 $0 \le U[j] < V[j] < N$
- 对于满足 $0 \le j \le N - 2$ 的每个 $j$，有 $1 \le T[j] \le 100$
- 可以通过这些道路从任意城市前往其他任意城市。
- 对于满足 $0 \le i < N$ 的每个 $i$，有 $0 \le W[i] \le 10^6$
- $1 \le Q \le 300\,000$
- $0 \le S < N$
- $0 \le X \le 10^6$
子任务
- （8 分）$N = 2$
- （21 分）$N, Q \le 1\,000$
- （14 分）对于满足 $0 \le j \le N - 2$ 的每个 $j$，有 $U[j] = \lfloor \frac{j}{2} \rfloor$ 且 $V[j] = j + 1$
- （21 分）对于满足 $0 \le j \le N - 2$ 的每个 $j$，有 $U[j] = j$ 且 $V[j] = j + 1$
- （36 分）无附加限制。
评测程序示例
评测程序示例按以下格式读取输入：
- 第 1 行：$N$ $Q$
- 第 2 行：$U[0]$ $U[1]$ $\dots$ $U[N - 2]$
- 第 3 行：$V[0]$ $V[1]$ $\dots$ $V[N - 2]$
- 第 4 行：$T[0]$ $T[1]$ $\dots$ $T[N - 2]$
- 第 5 行：$W[0]$ $W[1]$ $\dots$ $W[N - 1]$
- 第 $6 + k$ 行（$0 \le k < Q$）：第 $k$ 次更新的 $S$ $X$
评测程序示例按以下格式输出你的答案：
- 第 $1 + k$ 行（$0 \le k < Q$）：更新 $k$ 后
max_time的返回值