Maximizing Convenience Score in a Locked City Network

In Hungary there are \(N\) cities indexed from \(0\) to \(N-1\). The cities are connected by \(N-1\) bidirectional roads (indexed from \(0\) to \(N-2\)). For each road \(j\) (\(0 \le j \le N-2\)), it connects cities \(U[j]\) and \(V[j]\) with a travel time (or length) of \(W[j]\) units. It is guaranteed that the network is a tree, which means that for every pair of distinct cities there exists a unique path connecting them.

On the national holiday, citizens travel to two major celebration cities located in city \(X\) and city \(Y\). After the festivities, they return home. To avoid disruptions, the government assigns a non‐negative integer lockdown time \(c[i]\) to each city \(i\) (with \(0 \le i \le N-1\)) such that the total sum \(\sum_{i=0}^{N-1} c[i]\) does not exceed a given integer \(K\).

For a given lockdown assignment \(c\), we say that a city \(b\) is reachable from city \(a\) if one of the following holds:

1. \(b = a\).
2. There exists a unique path \(p_0, p_1, \ldots, p_t\) with \(p_0 = a\) and \(p_t = b\) such that for every \(i\) (\(1 \le i \le t\)), the cumulative distance from \(a\) to \(p_i\) (i.e. \(\sum_{j=0}^{i-1} \text{length}(p_j,p_{j+1})\)) does not exceed \(c[p_i]\). In other words, for each step on the path the condition \[ \text{distance}(a, p_i) \le c[p_i] \] must hold.

For any lockdown assignment the convenience score is defined as the sum of:

• Number of cities reachable from \(X\), and
• Number of cities reachable from \(Y\).

Note that if a city is reachable from both \(X\) and \(Y\) it counts twice. Your task is to choose a lockdown assignment \(c[0], c[1], \ldots, c[N-1]\) (with \(\sum_{i} c[i] \le K\)) so that the convenience score is maximized. It can be observed that if one were to set each \(c[i]\) to the minimum threshold needed to support reachability, then for a given source \(a\) and any city \(i\), we would need \(c[i] \geq \text{distance}(a, i)\). However, since the same assignment must serve both sources \(X\) and \(Y\), if a city \(i\) lies on paths from both sources, then it must satisfy \[ c[i] \geq \max(\,\text{distance}(X,i),\,\text{distance}(Y,i)\,). \]

In other words, if we decide to “activate” (i.e. have the minimum required lockdown time) a ball of cities from \(X\) (those with \(\text{distance}(X,i) \le r_X\)) and similarly a ball from \(Y\) (with radius \(r_Y\)), then the total cost contributed by a city \(i\) is:

• If \(i\) is in both balls: \(\max(\text{distance}(X,i), \text{distance}(Y,i))\).
• If \(i\) is only in one ball: the corresponding distance.
• If \(i\) is in neither, cost is \(0\).

Your goal is to choose two radii \(r_X\) and \(r_Y\) (and set the corresponding \(c[i]\) values along the required paths) so that the overall cost does not exceed \(K\) while achieving the maximum possible convenience score, which is the sum of the counts of cities in the two balls.

Input Format: The input begins with four space‐separated integers \(N,\ K,\ X,\ Y\). Then \(N-1\) lines follow, each containing three integers \(U[j],\ V[j],\ W[j]\) representing a road between cities \(U[j]\) and \(V[j]\) with length \(W[j]\).

Output Format: Output one integer—the maximum convenience score achievable by some lockdown assignment.

inputFormat

The first line contains four integers \(N, K, X, Y\) (where \(0 \le X, Y \le N-1\)). Each of the following \(N-1\) lines contains three integers \(U[j], V[j], W[j]\) indicating a bidirectional road between cities \(U[j]\) and \(V[j]\) with length \(W[j]\). It is guaranteed that the given roads form a tree.

outputFormat

Output a single integer representing the maximum convenience score achievable subject to the budget constraint \(K\).

sample

3 5 0 1
0 2 2
1 2 1

5