题目描述

匈牙利有 $N$ 个城市，编号依次为 $0$ 到 $N-1$。

这些城市之间由 $N-1$ 条双向道路连接，编号为 $0$ 至 $N-2$。对每个 $j$（$0 \le j \le N-2$），第 $j$ 条道路连接城市 $U[j]$ 和城市 $V[j]$，其长度为 $W[j]$，表示这两个城市之间的交通时间为 $W[j]$ 个时间单位。每条道路连接两个不同的城市，且每两个城市之间最多由一条道路连接。

两个不同城市 $a$ 和 $b$ 之间的一条路径是一个由不同城市组成的序列 $p_0, p_1, \ldots, p_t$，满足以下条件：

1. $p_0 = a$，$p_t = b$；
2. 对每个 $i$（$0 \le i \lt t$），存在一条道路连接 $p_i$ 和 $p_{i+1}$。

利用这些道路从任意一个城市到任意一个其他的城市都是有可能的，且任意两个不同城市之间的路径是唯一的。

一条路径 $p_0, p_1, \ldots, p_t$ 的长度是这条路径上连接相邻城市的 $t$ 条道路的长度之和。

在建国日，政府会在特定时刻封锁城市。每个城市被分配一个非负的封锁时刻 $c[i]$（$0 \leq i \leq N-1$），且所有 $c[i]$ 之和不得超过 $K$。

考虑城市 $a$ 和某个封锁时刻分配方案，城市 $b$ 是从城市 $a$ 可达的，当且仅当满足以下两种情况之一：

• 情况 1：$b = a$；
• 情况 2：$a$ 与 $b$ 之间的路径 $p_0, \ldots, p_t$（$p_0 = a$ 且 $p_t = b$）满足：路径 $p_0, p_1$ 的长度 $\leq c[p_1]$，路径 $p_0, p_1, p_2$ 的长度 $\leq c[p_2]$，……，路径 $p_0, p_1, \ldots, p_t$ 的长度 $\leq c[p_t]$。

今年，两个主要庆祝地点位于城市 $X$ 和 $Y$。对于每一个封锁时刻分配方案，便利分数定义为“从 $X$ 可达的城市个数”与“从 $Y$ 可达的城市个数”之和（若一个城市从 $X$ 和 $Y$ 均可达，计算两次）。

你的任务是计算能被某个封锁时刻分配方案实现的最大便利分数。

实现细节

你需要在程序开始引入库 closing.h，并实现以下函数：

int max_score(int N, int X, int Y, int64 K, int[] U, int[] V, int[] W)

参数说明

• $N$：城市的个数；
• $X, Y$：两个主要庆祝城市的编号；
• $K$：封锁时刻总和的上界；
• $U, V$：长度为 $N-1$ 的数组，描述道路连接情况（第 $j$ 条道路连接 $U[j]$ 和 $V[j]$）；
• $W$：长度为 $N-1$ 的数组，描述道路长度（第 $j$ 条道路的长度为 $W[j]$）。

返回要求

返回能被某个封锁时刻分配方案实现的最大便利分数。每个测试用例可多次调用该函数。

例子

例子 1

考虑以下函数调用：

max_score(7, 0, 2, 10,
          [0, 0, 1, 2, 2, 5], [1, 3, 2, 4, 5, 6], [2, 3, 4, 2, 5, 3])

这对应以下道路网络：

假设封锁时刻如下分配：

城市	$0$	$1$	$2$	$3$	$4$	$5$	$6$
封锁时刻 $c[i]$	$0$	$4$	$0$	$3$	$2$	$0$

注意所有封锁时刻之和为 9，不超过 K = 10。城市 0, 1 和 3 都是从城市 X (X = 0) 可达的，而城市 1, 2 和 4 都可以从城市 Y (Y = 2) 可达。 因此，便利分数为 3+3 = 6。不存在封锁时刻分配方案使得便利分数大于 6，所以该函数应该返回 6。

例子 2

考虑以下函数调用：

max_score(4, 0, 3, 20, [0, 1, 2], [1, 2, 3], [18, 1, 19])

假设封锁时间如下分配：

城市	$0$	$1$	$2$	$3$
封锁时刻 $c[i]$	$0$	$1$	$19$	$0$

城市 0 从城市 X (X = 0) 可达，而城市 2 和 3 都是可以从城市 Y (Y=3) 可达的。因此，便利分数是 1 + 2 = 3。不存在封锁时刻分配方案使得便利分数大于 3，所以函数应该返回 3。

约束条件

• $2 \le N \le 200000$；
• $0 \le X \lt Y \lt N$；
• $0 \le K \le 10^{18}$；
• 对每个 $j$（$0 \le j \le N-2$），$0 \le U[j] \lt V[j] \lt N$；
• 对每个 $j$（$0 \le j \le N-2$），$1 \le W[j] \le 10^6$；
• 城市间道路构成连通图；
• 所有调用 max_score 的 $N$ 之和 $S_N \le 200000$。

子任务

若道路网络是线性的（即第 $i$ 条道路连接城市 $i$ 和 $i+1$，$0 \le i \le N-2$），则对应以下子任务： | 子任务 | 附加限制 | 分值 | |--------|----------|------| | 1 | 从 $X$ 到 $Y$ 的路径长度 $> 2K$ | $8$ | | 2 | $S_N \le 50$，道路网络线性 | $9$ | | 3 | $S_N \le 500$，道路网络线性 | $12$ | | 4 | $S_N \le 3000$，道路网络线性 | $14$ | | 5 | $S_N \le 20$ | $9$ | | 6 | $S_N \le 100$ | $11$ | | 7 | $S_N \le 500$ | $10$ | | 8 | $S_N \le 3000$ | $10$ | | 9 | 无额外约束 | $17$ |

评测程序示例

输入格式

• 第 $1$ 行：$C$（场景数，即调用 max_score 的次数）；
• 接下来 $C$ 个场景，每个场景格式如下：
  • 第 $1$ 行：$N \; X \; Y \; K$；
  • 第 $2+j$ 行（$0 \le j \le N-2$）：$U[j] \; V[j] \; W[j]$。

输出格式

对每个场景，输出一行 max_score 的返回值。