Closing Time

문제

Hungary is a country with $NN$ cities, numbered from $00$ to $N-1N\; -\; 1$.

The cities are connected by $N-1N\; -\; 1$ bidirectional roads, numbered from $00$ to $N-2N\; -\; 2$. Road $jj$ (0 ≤ j ≤ N - 2) connects city $U[j]U[j]$ and city $V[j]V[j]$ and has length $T[j]T[j]$, that is, it allows one to travel between the cities in $T[j]T[j]$ units of time. Each road connects two different cities, and each pair of cities is connected by at most one road.

A path between two distinct cities $aa$ and $bb$ is a sequence of distinct cities $p_0,p_1,\dots ,p_{l}p\_0\; ,\; p\_1\; ,\; \backslash dots\; ,\; p\_l$ such that:

• $p_0=ap\_0\; =\; a$,
• $p_l=bp\_l\; =\; b$,
• for each $ii$ (0 &le; i < l), there is a road connecting cities $p_{i}p\_i$ and $p_{i+1}p\_\{i+1\}$.

It is possible to travel from any city to any other city by using the roads, that is, there is a path between every two distinct cities. Note that the path connecting any pair of cities is unique.

The length of a path $p_0,p_1,\dots ,p_{t}p\_0\; ,\; p\_1\; ,\; \backslash dots,\; p\_t$ is the sum of the lengths of the $tt$ roads connecting consecutive cities along the path.

In Hungary, many people travel to attend the Foundation Day festivities in two major cities. Once the celebrations are over, they return to their homes. The government wants to prevent the crowd from disturbing the locals, so they plan to lock down all cities at certain times. Each city will be assigned a non-negative closing time by the government. The government has decided that the sum of all closing times must not be more than $KK$. More precisely, for every $ii$ between $00$ and $N-1N\; -\; 1$, inclusive, the closing time assigned to city $ii$ is a nonnegative integer $c[i]c[i]$. The sum of all $c[i]c[i]$ must not be greater than $KK$.

Consider a city $aa$ and some assignment of closing times. We say that a city $bb$ is reachable from city $aa$ if and only if either $b=ab\; =\; a$, or the path $p_0,\dots ,p_{t}p\_0\; ,\; \backslash dots\; ,\; p\_t$ between these two cities (so in particular $p_0=ap\_0\; =\; a$ and $p_t=bp\_t\; =\; b$) satisfies the following conditions:

• the length of the path $p_0,p_{1}p\_0,\; p\_1$ is at most $c[p_1]c[p\_1]$, and
• the length of the path $p_0,p_1,p_{2}p\_0,\; p\_1,\; p\_2$ is at most $c[p_2]c[p\_2]$, and
• $\dots \backslash dots$
• the length of the path $p_0,p_1,p_2,\dots ,p_{t}p\_0\; ,\; p\_1\; ,\; p\_2\; ,\backslash dots\; ,\; p\_t$ is at most $c[p_t]c[p\_t]$.

This year, the two main festival sites are located in city $XX$ and city $YY$. For each assignment of closing times, the convenience score is defined as the sum of the following two numbers:

• The number of cities reachable from city $XX$.
• The number of cities reachable from city $YY$.

Note that if a city is reachable from city $XX$ and reachable from city $YY$, it counts twice towards the convenience score.

Your task is to compute the maximum convenience score that can be achieved by some assignment of closing times.