문제
1번 노드가 루트이고 노드가 N개 있는 트리가 있다. 처음에는 모든 노드의 가중치가 0이지만 쿼리를 통해서 일부 노드가 바뀐다. 나올 수 있는 쿼리는 다음과 같다.
쿼리 1: A번 노드의 가중치를 X로 바꾼다.
쿼리 2: A번 노드의 서브트리에 포함하는 모든 노드의 가중치의 합을 구한다.
두 종류의 쿼리를 빠르게 수행하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 노드의 수 N (2 ≤ N ≤ 300,000)가 주어진다.
두 번째 줄부터 N-1개의 줄에는 트리의 각 간선이 연결하는 두 정점의 번호가 주어진다.
N+1번째 줄에는 쿼리의 수 Q (1 ≤ Q ≤ 300,000)가 주어진다.
N+2번째 줄부터 Q개의 줄에는 쿼리가 주어진다. 쿼리 1은 1 A X로, 쿼리 2는 2 A로 주어진다. (1 ≤ A ≤ N, 0 ≤ X ≤ 300)가 주어진다.
출력
쿼리 2의 정답을 한 줄에 하나씩 출력한다. 채점 데이터에서 쿼리 2는 항상 하나 이상 존재한다.
예제 #1
5
1 2
2 3
3 4
2 5
4
1 3 5
2 1
1 5 3
2 2
5
8
예제 #2
24
1 8
2 17
3 15
4 14
5 8
6 3
7 15
8 23
9 20
10 4
11 3
12 20
13 4
14 17
15 1
16 14
17 1
18 15
19 23
20 17
21 7
22 4
23 24
15
1 2 3
1 11 111
2 1
1 19 91
1 7 6
2 15
1 11 1
1 12 8
2 20
1 1 11
1 23 45
2 5
1 8 18
1 19 9
2 1
114
117
8
0
101
태그
로그인해야 코드를 작성할 수 있어요.