The Guardian of Balance

Interview

Time limit1.5sMemory limit1024 MB

Summary

Given a weighted tree, find the vertex whose distances to all vertices have the smallest variance, breaking ties by the smaller vertex number.

Level: Medium6 of 10
Topics: Tree, Dynamic programming, DFS
Solved: No attempts yet

Problem

Kyeongin, the guardian of balance, is given a tree with $N$ vertices. To balance the tree, Kyeongin picks a root as follows.

Let $V_i$ be the variance of the distances from vertex $i$ to all vertices. Pick the vertex with the smallest $V_i$ as the root. If several vertices tie, pick the one with the smallest number.

Find the root Kyeongin will pick.

Input

The first line contains the number of vertices $N$ . $(1 \le N \le 200\,000)$

Each of the next $N-1$ lines contains three integers $u$ , $v$ , and $w$ separated by spaces. This means there is an edge of length $w$ between vertices $u$ and $v$ . $(1 \le u, v \le N; u \neq v; 1 \le w \le 10\,000)$

Output

Print the root Kyeongin will pick.

Hint

Be careful that intermediate values do not become too small or too large during the calculation.

Mean: $\mathrm{E}[X]=\frac{1}{|X|}\sum\limits_{x \in X}x$
Variance: $\mathrm{Var}[X]=\mathrm{E}[(X-\mathrm{E}[X])^2]=\frac{1}{|X|}\sum\limits_{x \in X}(x-\mathrm{E}[X])^2$

Examples1

Example 1
Input
```
4
1 2 8
1 3 8
3 4 9
```
Expected output
```
3
```