뿌리째 흔드는 숲
다이아몬드 II의견: 0
\(N\)개의 정점으로 이루어진 숲(forest)이 있다. 처음에는 간선이 하나도 없으며, 각 정점 \(i\)에는 정수 값 \(a_i\)가 적혀 있다.
다음 네 종류의 연산을 총 \(Q\)번 처리해야 한다.
-
1 u v: 정점 \(u\)와 \(v\)를 잇는 간선을 추가한다. (\(u\)와 \(v\)가 서로 다른 트리에 속함이 보장된다.) -
2 u v: 정점 \(u\)와 \(v\)를 잇는 간선을 제거한다. (해당 간선이 존재함이 보장된다.) -
3 v x: 정점 \(v\)의 값을 \(x\)로 바꾼다. -
4 r v: 정점 \(v\)가 속한 트리를 정점 \(r\)을 뿌리로 하여 매달았을 때, 정점 \(v\)의 서브트리에 속한 모든 정점의 값의 합을 출력한다. (\(r\)과 \(v\)는 같은 트리에 속함이 보장되며, \(r = v\)이면 트리 전체의 값의 합이 된다.)
정점 \(v\)의 서브트리란, 뿌리 \(r\)에서 각 정점으로 가는 유일한 경로가 모두 \(v\)를 거쳐야 하는 정점들의 집합(\(v\) 자신 포함)이다.
\(1 \le N \le 50{,}000\)
\(1 \le Q \le 50{,}000\)
\(-10^9 \le a_i \le 10^9\)
\(3\)번 연산의 \(x\)는 \(-10^9 \le x \le 10^9\)
각 연산의 정점 번호는 \(1\) 이상 \(N\) 이하이다. 연산은 위에 명시된 조건(서로 다른 트리, 간선 존재, 같은 트리)을 항상 만족한다.
첫 줄에 정점의 수 \(N\)과 연산의 수 \(Q\)가 주어진다.
둘째 줄에 \(N\)개의 정수 \(a_1, a_2, \dots, a_N\)이 주어진다.
이어서 \(Q\)개의 줄에 위 형식의 연산이 한 줄에 하나씩 주어진다.
각 4 연산에 대해 서브트리 값의 합을 한 줄에 하나씩 출력한다.
5 8
1 2 3 4 5
1 1 2
1 2 3
1 2 4
4 1 2
4 2 1
3 4 10
4 1 2
4 3 1
9
1
15
1값 [1,2,3,4,5]. 간선 1-2, 2-3, 2-4를 추가한다(정점 5는 외톨이). 1을 뿌리로 하면 2의 서브트리는 {2,3,4}로 합 2+3+4=9. 2를 뿌리로 하면 1의 서브트리는 {1}뿐이라 합 1. 정점 4의 값을 10으로 바꾸면 1을 뿌리로 한 2의 서브트리 합은 2+3+10=15. 3을 뿌리로 하면 1의 서브트리는 {1}이라 합 1.
2 6
7 -3
4 1 1
1 1 2
4 1 1
4 2 1
3 1 100
4 2 2
7
4
7
97값 [7,-3]. 처음 정점 1만으로 된 트리에서 1의 서브트리 합은 7. 1-2를 연결하면 1을 뿌리로 한 1의 서브트리는 트리 전체 {1,2}로 7+(-3)=4, 2를 뿌리로 한 1의 서브트리는 {1}이라 7. 정점 1을 100으로 바꾸면 2를 뿌리로 한 2의 서브트리는 전체 {1,2}로 100+(-3)=97.
riseoj 작성
출처 Original
평가 및 의견
뿌리째 흔드는 숲
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
뿌리째 흔드는 숲