P9600 [IOI 2023] Blockade Moments

This is an interactive problem. You only need to implement the function required in the code. Your code does not need to include any additional header files, and you do not need to implement the `main` function. This problem only supports submissions in C++.

There are $N$ cities in Hungary, numbered from $0$ to $N - 1$. These cities are connected by $N - 1$ bidirectional roads, numbered from $0$ to $N - 2$. For each $j$ ($0 \le j \le N - 2$), road $j$ connects city $U[j]$ and city $V[j]$, and has length $W[j]$, meaning the travel time between these two cities is $W[j]$ time units. Each road connects two different cities, and between any two cities there is at most one road. A **path** between two different cities $a$ and $b$ is a sequence of distinct cities $p_0, p_1, \ldots, p_t$ satisfying: * $p_0 = a$, * $p_t = b$, * for each $i$ ($0 \le i \lt t$), there is a road connecting $p_i$ and $p_{i + 1}$. Using these roads, it is possible to travel from any city to any other city. In other words, there is a path between any two different cities. It can be proven that the path between any two different cities is unique. The **length** of a path $p_0, p_1, \ldots, p_t$ is the sum of the lengths of the $t$ roads connecting consecutive cities along the path. In Hungary, many people attend celebrations held in two major cities on National Day. When the celebrations end, they go home. To prevent crowds from disturbing local residents, the government decided to block cities at certain moments. Each city is assigned a non-negative **blockade moment**. The government decided that the sum of blockade moments of all cities must not exceed $K$. Specifically, for each $i$ ($0 \leq i \leq N - 1$), the blockade moment assigned to city $i$ is a non-negative integer $c[i]$. The sum of all $c[i]$ does not exceed $K$. Consider a city $a$ and an assignment of blockade moments. We say that a city $b$ is reachable from city $a$ if and only if at least one of the following two cases holds. Case 1: $b = a$. Case 2: The path $p_0, \ldots, p_t$ between the two cities ($p_0 = a$ and $p_t = b$) satisfies: * the length of the path $p_0, p_1$ is at most $c[p_1]$, and * the length of the path $p_0, p_1, p_2$ is at most $c[p_2]$, and * $\ldots$ * the length of the path $p_0, p_1, p_2, \ldots, p_t$ is at most $c[p_t]$. This year, the two main celebration locations are in cities $X$ and $Y$. For each assignment of blockade moments, we define a **convenience score** as the sum of the following two numbers: - the number of cities reachable from city $X$, - the number of cities reachable from city $Y$. Note that if a city is reachable from both city $X$ and city $Y$, then it is counted twice when computing the convenience score. Your task is to compute the maximum convenience score that can be achieved by some assignment of blockade moments.

Let $C$ be the number of scenarios, i.e. the number of calls to `max_score`. The grader reads the input in the following format: * Line $1$: $C$ The following are the descriptions of the $C$ scenarios. The grader reads the description of each scenario in the following format: * Line $1$: $N \; X \; Y \; K$ * Line $2 + j$ ($0 \le j \le N - 2$): $U[j] \; V[j] \; W[j]$

For each scenario, the grader prints a separate line in the following format: * Line $1$: the return value of `max_score`

#### Implementation Details You need to implement the following function. ``` int max_score(int N, int X, int Y, int64 K, int[] U, int[] V, int[] W) ``` * $N$: the number of cities. * $X$, $Y$: the two major celebration cities. * $K$: the upper bound on the total sum of blockade moments. * $U$, $V$: arrays of length $N - 1$ describing the road connections. * $W$: an array of length $N - 1$ describing the road lengths. * The function should return the maximum convenience score achievable by some assignment of blockade moments. * This function may be called multiple times for each test case. #### Examples Consider the following call: ``` max_score(7, 0, 2, 10, [0, 0, 1, 2, 2, 5], [1, 3, 2, 4, 5, 6], [2, 3, 4, 2, 5, 3]) ``` This corresponds to the following road network:  Suppose the blockade moments are assigned as follows: | **City** | $0$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | |:--------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:| | **Blockade moment** | $0$ | $4$ | $0$ | $3$ | $2$ | $0$ | $0$ | Note that the sum of all blockade moments is $9$, which does not exceed $K = 10$. Cities $0$, $1$, and $3$ are reachable from city $X$ ($X = 0$), and cities $1$, $2$, and $4$ are reachable from city $Y$ ($Y = 2$). Therefore, the convenience score is $3 + 3 = 6$. There is no assignment of blockade moments that makes the convenience score greater than $6$, so the function should return $6$. Consider another call: ``` max_score(4, 0, 3, 20, [0, 1, 2], [1, 2, 3], [18, 1, 19]) ``` This corresponds to the following road network:  Suppose the blockade moments are assigned as follows: | **City** | $0$ | $1$ | $2$ | $3$ | |:--------:|:---:|:---:|:---:|:---:| | **Blockade moment** | $0$ | $1$ | $19$ | $0$ | City $0$ is reachable from city $X$ ($X = 0$), and cities $2$ and $3$ are reachable from city $Y$ ($Y = 3$). Therefore, the convenience score is $1 + 2 = 3$. There is no assignment of blockade moments that makes the convenience score greater than $3$, so the function should return $3$. #### Constraints * $2 \le N \le 200\,000$ * $0 \le X \lt Y \lt N$ * $0 \le K \le 10^{18}$ * $0 \le U[j] \lt V[j] \lt N$ (for each $j$ with $0 \le j \le N - 2$) * $1 \le W[j] \le 10^6$ (for each $j$ with $0 \le j \le N - 2$) * Using these roads, you can travel from any city to any other city. * $S_N \le 200\,000$, where $S_N$ is the sum of $N$ over all calls to `max_score`. #### Subtasks We say a road network is **linear** if road $i$ connects city $i$ and city $i + 1$ (for each $i$ with $0 \le i \le N - 2$). 1. (8 points) The length of the path from city $X$ to city $Y$ is greater than $2K$. 1. (9 points) $S_N \le 50$, and the road network is linear. 1. (12 points) $S_N \le 500$, and the road network is linear. 1. (14 points) $S_N \le 3\,000$, and the road network is linear. 1. (9 points) $S_N \le 20$. 1. (11 points) $S_N \le 100$. 1. (10 points) $S_N \le 500$. 1. (10 points) $S_N \le 3\,000$. 1. (17 points) No additional constraints. Translated by ChatGPT 5