자손에게 물려주기
골드 I의견: 0
정점이 \(N\)개인 트리가 있다. 트리는 정점 \(1\)을 루트로 한다. 모든 정점의 값은 처음에 \(0\)이다.
정점 \(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\)이 주어진다. 다음 \(N-1\)개의 줄에 간선의 정보가 주어진다 — 각 줄의 \(a\ b\)는 정점 \(a\)와 \(b\)를 잇는 간선을 뜻한다. 트리는 정점 \(1\)을 루트로 한다. 그 다음 줄에 쿼리의 개수 \(Q\)가 주어지고, 이후 \(Q\)개의 줄에 위 형식의 쿼리가 주어진다.
각 2 v 쿼리마다 한 줄에 정점 \(v\)의 현재 값을 출력한다.
5
1 2
1 3
2 4
2 5
6
1 2 5
2 4
2 3
1 1 1
2 4
2 1
5
0
6
1
\(2\)의 서브트리 \(\{2,4,5\}\)에 \(5\)를 더하면 \(4\)의 값은 \(5\), \(3\)의 값은 \(0\)이다. 이어서 \(1\)의 서브트리(전체)에 \(1\)을 더하면 \(4\)의 값은 \(6\), \(1\)의 값은 \(1\)이 된다.
1
5
2 1
1 1 9
2 1
1 1 -4
2 1
0
9
5
정점이 하나뿐인 트리. \(0\)에서 \(9\)를 더하면 \(9\), 다시 \(4\)를 빼면 \(5\)이다.
플래티넘 IV막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
자손에게 물려주기
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
자손에게 물려주기