시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 1024 MB | 100 | 33 | 26 | 37.681% |
$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개의 줄에 순서대로 출력한다.
7 1 6 1 7 7 3 3 2 7 5 5 4 4 1 2 1 4 1 6 2 6 7
2 7 7 1