서브트리 합

골드 I

난이도

시간 제한

256MB

메모리 제한

맞았습니다!!

제출 수

0.0%

정답률

레이팅

의견: 0

설명

정점이 $$N$$ 개인 트리가 있다. 트리는 정점 $$1$$ 을 루트로 한다. 각 정점에는 정수 값이 하나씩 적혀 있다.

정점 $$v$$ 의 서브트리란 $$v$$ 자신과, 루트에서 $$v$$ 를 거쳐야만 도달할 수 있는 모든 정점들의 집합이다.

다음 두 종류의 쿼리를 처리하여라.

1 v x — 정점 $$v$$ 에 적힌 값에 $$x$$ 를 더한다.
2 v — 정점 $$v$$ 의 서브트리에 속한 모든 정점의 값의 합을 출력한다.

제약

$1 \le N \le 100\,000$ , $1 \le Q \le 100\,000$ . 각 값과 $$x$$ 의 절댓값은 $$10^9$$ 이하이다. 모든 답은 64비트 정수 범위 안에 들어간다.

입력 형식

첫째 줄에 정점의 개수 $$N$$ 이 주어진다. 둘째 줄에 정점 $$1$$ 부터 $$N$$ 까지의 초기 값 $$N$$ 개가 공백으로 구분되어 주어진다. 셋째 줄에 간선의 정보가 $$N-1$$ 개의 줄에 걸쳐 주어진다 — 각 줄의 $a\ b$ 는 정점 $$a$$ 와 $$b$$ 를 잇는 간선을 뜻한다. 트리는 정점 $$1$$ 을 루트로 한다. 그 다음 줄에 쿼리의 개수 $$Q$$ 가 주어지고, 이후 $$Q$$ 개의 줄에 위 형식의 쿼리가 주어진다.

출력 형식

각 2 v 쿼리마다 한 줄에 서브트리의 값의 합을 출력한다.

예제 1

입력

출력

설명

처음 $$2$$ 의 서브트리는 $\{2,4,5\}$ 로 합은 $$2+4+5=11$$ , $$1$$ 의 서브트리는 전체로 합은 $$15$$ 이다. $$4$$ 의 값에 $$10$$ 을 더하면 $$2$$ 의 서브트리 합은 $$21$$ , $$1$$ 의 서브트리 합은 $$25$$ 가 된다.