트리와 쿼리 17

$N$개의 정점으로 이루어진 트리가 있다. 정점은 1번부터 $N$번까지 번호가 매겨져 있고, 1번 정점은 루트이다. 각 정점 $i$에는 정수 $A\[i]$가 저장되어 있다. 가장 처음에 $A\[i]$는 0이다.

다음과 같은 쿼리를 수행해야 한다.

• 1 u: 정점 $u$를 루트로 하는 서브 트리의 모든 정점 $i$의 $A\[i]$에 1을 더한다.
• 2 u v: 정점 $u$에서 정점 $v$로 가는 유일한 최단 경로에 있는 모든 정점 $i$의 $A\[i]$에 1을 더한다. $u$와 $v$는 같을 수도 있다.

각각의 쿼리를 수행한 후 $\sum\_{y = 1}^{N} A\[y] \times dist(x, y)$ 의 값을 가장 작게 만드는 정점 $x$를 출력한다. $dist(x, y)$ 는 $x$에서 $y$로 가는 경로에 존재하는 간선의 개수와 같다. 가능한 정점 x가 여러가지면, 루트에서 거리가 가장 가까운 정점을 출력한다. 그러한 정점은 항상 유일하다는 것을 증명할 수 있다.

첫째 줄에 $N$이 주어진다. ($2 \le N \le 100\\,000$)

다음 $N-1$개의 줄에는 트리의 간선이 주어진다. 각 줄은 공백으로 구분된 두 정수 $u$와 $v$가 주어지고, 정점 $u$와 정점 $v$를 연결하는 간선을 의미한다. ($1 \le u, v \le N, u \neq v$)

다음 줄에는 수행해야 하는 쿼리의 개수 $Q$가 주어진다. ($1 \le Q \le 100\\,000$).

다음 $Q$개의 줄에는 쿼리가 한 줄에 하나씩 주어지며, 쿼리는 다음과 같은 형식이다.

• 1 u ($1 \le u \le N$)
• 2 u v ($1 \le u, v \le N$)

쿼리를 수행한 후 출력해야 하는 값을 Q개의 줄에 순서대로 출력한다.