시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 88 | 28 | 17 | 24.286% |
N개의 정점으로 이루어진 트리가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, i번 정점에는 정수 Ai가 저장되어 있다. 처음 상태에서 Ai=0이다. (1 ≤ i ≤ N)
당신은 다음과 같은 쿼리를 총 Q번 수행해야 한다.
1 u v
: 트리의 루트를 정점 u라 하였을 때, 정점 v를 루트로 하는 서브트리의 모든 정점 i의 Ai에 1을 더한다.2 u v
: 정점 u에서 정점 v로 가는 유일한 경로에 있는 모든 정점 i의 Ai에 1을 더한다.3 v
: $\sum_{i = 1}^{N} A_i \times dist(v, i)$를 출력한다. $dist(x, y)$는 정점 x에서 정점 y로 가는 경로에 있는 간선의 수를 의미한다.첫째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000)
다음 N-1개 줄에 트리의 간선이 주어진다. 각 줄에는 공백으로 구분된 두 수 u와 v가 주어지고, u와 v를 연결하는 간선이 있다는 것을 의미한다. (1 ≤ u, v ≤ N)
다음 줄에는 쿼리의 개수 Q가 주어진다. (1 ≤ Q ≤ 200,000)
다음 Q개의 줄에는 한 줄에 하나씩 다음과 같은 형식 중 하나로 쿼리가 주어진다.
1 u v
(1 ≤ u, v ≤ N)2 u v
(1 ≤ u, v ≤ N)3 v
(1 ≤ v ≤ N)3번 쿼리는 한 번 이상 주어진다.
각각의 3번 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.
5 4 2 2 5 1 5 1 3 5 2 2 4 3 4 2 1 5 2 5 5 3 2
1 5
Camp > Petrozavodsk Programming Camp > Winter 2021 > Day 9: Grand Prix of Suwon A번
Contest > Open Cup > 2020/2021 Season > Stage 13: Grand Prix of Suwon A번