35140번 - Mediation 다국어

You are the mayor of a tree-structured city with $N$ districts, numbered from $1$ to $N$, connected by $N - 1$ roads, numbered from $1$ to $N - 1$. Road $i$ connects district $U_i$ and district $V_i$ bidirectionally with weight $W_i$. Two districts $S_1$ and $S_2$ have been marked as mediator districts. The travel cost between district $x$ and district $y$, denoted by $d(x, y)$, is the minimum sum of weights of the roads you need to pass through.

Whenever a conflict arise between any two districts, the mediator districts are required to travel to the conflicting districts. The mediation cost for two conflicting districts $u$ and $v$, denoted by $M(u, v)$, is the maximum travel cost of the mediator districts to the nearest conflicting district. Formally, $M(x, y)$ can be calculated as follows.

\[M(u, v) = \max(\min(d(u, S_1), d(v, S_1)), \min(d(u, S_2), d(v, S_2)))\]

Calculate the sum of mediation cost $M(u, v)$ over all $1 \leq u < v \leq N$.

The first line contains three integers: $N$, $S_1$, and $S_2$ ($2 \le N \le 200\,000$; $1 \leq S_1 < S_2 \leq N$).

The next $N-1$ lines contains integers $U_i$, $V_i$, and $W_i$ ($1 \le U_i < V_i \le N$; $1 \leq W_i \leq 100$) describing an edge.

Output the sum of mediation cost in a single line.

Explanation of Sample 1: The city is illustrated as follows.

The values of $M(u, v)$ over all $1 \leq u < v \leq N$ are presented as follows.

The sum of all $M(u, v)$ is 35.