레몬향의 마흐트

레몬향의 마흐트, 뎅켄의 스승이자 칠붕현 중 하나. 그는 모든 것을 레몬으로 만들어버리는 마법으로 유명하다. 대마법사 프리렌은, 레몬으로 변해버린 뎅켄의 고향을 원래 상태로 되돌리기 위해 마흐트의 마법을 해주해야 한다.

마흐트의 마법진은, 루트가 $1$인 정점 $N$개로 이루어진 트리의 형태를 띤다. 각 간선은 유향 간선으로, 자식에서 부모 방향으로 향한다. 특히, $i$번 간선은 $b_i$로부터 $a_i$로 향하는 용량 $w_i$의 간선이다. $(a_i < b_i, 1 \leq w_i \leq 10^5)$

프리렌은, 해주를 위해 모든 간선들 중 가장 용량이 가장 작은 간선의 용량을 구해야 한다. 즉, $w_i$의 최솟값을 구해야 한다. 하지만, $N$, $a_i$와 $b_i$만 알 뿐, $w_i$는 알지 못한다. 그렇기에, 프리렌은 마력 조작을 통해 마력에 대한 정보를 알아내야 한다. 마력 조작은 최대 $200$번 할 수 있으며, 각 마력 조작은 다음과 같이 진행된다.

1. 간선 중 몇 개를 골라, 간선의 용량 $w_i$를 $10^{10}$으로 바꾼다.
2. 각 정점에 흘려보낼 마력량을 정한다. 즉, 길이 $N$의 $0$ 이상 $10^5$ 이하의 정수로 이루어진 배열을 하나 정의해 $i$번 정점에 $A_i$만큼의 마력을 흘려보낸다.

이렇게 하면, 정점 $i$에는 마력이 $f(i) = A_i\,+\,(i$로 향하는 모든 정점 $j$에 대해, $i$와 $j$사이의 용량 $W$에 대해 $\sum \min(W, f(j)))$ 만큼 흐르게 된다.

1. 마력을 흘려보낸 후, 프리렌은 루트에 흐르는 마력 $f(1)$을 알 수 있다.

각 마력 조작은 독립적임에 주의하라. 즉, 마력 조작이 끝난 후에는 마법진이 즉시 원상태로 복구된다.

프리렌을 도와, 마흐트의 마법을 해주해주자.

첫째 줄에 $N$이 주어진다.

둘째 줄부터 $N$번 줄까지 $N-1$개 줄에 걸쳐 $i+1$번 줄에 두 정수 $a_i$, $b_i$가 공백을 사이에 두고 주어진다.

전체 문제에서, $2 \leq N \leq 5 \times 10^4, a_i < b_i, 1 \leq w_i \leq 10^5$

$a_i = i, b_i = i+1$ (10점) $\\$ $a_i = [(i+1)/2], b_i = i+1$ (17점) $\\$ $a_i = 1, b_i = i+1$ (21점) $\\$ $N \leq 3 \times 10^3$. (42점) $\\$ 추가 제한 없음. (12점) $\\$