#327 동적 트리 정점 더하기 서브트리 합

문제

지문 언어

$N$ 개의 정점으로 이루어진 트리가 주어진다. 정점은 $0,1,\cdots,N-1$ 번으로 번호가 붙어 있으며, 처음에 $i$ 번 정점에는 값 $a_i$ 가 적혀 있다.

다음 $Q$ 개의 질의를 순서대로 처리하여라. 모든 질의를 처리하는 동안, 각 질의가 끝난 뒤의 그래프는 항상 트리임이 보장된다.

입력은 다음과 같은 형식으로 주어진다.

$N\ Q$ $a_0\ a_1\ \cdots\ a_{N-1}$

2번 질의마다, 요구한 정점 값의 합을 한 줄에 하나씩 출력한다.

#	점수	제한
1	12	$N,Q \leq 2\ 000$ .
2	18	`0`번 질의가 없다.
3	25	모든 `0`번 질의에서 삭제되는 간선은 현재 트리의 리프에 연결되어 있고, 그 리프가 새로 추가되는 간선의 한쪽 끝점이다.
4	45	추가적인 제약조건이 없다.

입력

7
10 100 1000 10000
1
2
3
4
1 2
1 100000
1 2
1 2 2 0
0 2
2 3 3 1
1 4

출력

첫 번째 질의에서는 간선 $(1,2)$ 를 기준으로 $1$ 번 정점 쪽 컴포넌트에 $0,1,4$ 번 정점이 있으므로 합은 $1+10+10000=10011$ 이다.