회사 조직도
플래티넘 IV의견: 0
어떤 회사의 조직도는 사장(정점 \(1\)번)을 뿌리로 하는 트리로 주어진다. 각 직원에게는 초기 점수가 매겨져 있다.
직원 \(v\)의 부서란 \(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\)가 직접 연결되어 있다는 뜻이다. 그다음 줄에는 \(n\)개의 정수가 공백으로 구분되어 주어지며, \(i\)번째 수는 직원 \(i\)번의 초기 점수이다. 그다음 줄에 쿼리의 개수 \(q\)가 주어지고, 이후 \(q\)개의 줄에 위 형식의 쿼리가 주어진다.
각 2 v 쿼리마다 한 줄에 부서 점수의 합을 출력한다.
5
1 2
1 3
3 4
3 5
1 2 3 4 5
6
2 1
2 3
1 3 10
2 3
2 1
2 5
15
12
42
45
15
처음 \(1\)번의 서브트리는 모든 정점이고 합은 \(15\), \(3\)번의 서브트리 \(\{3,4,5\}\)의 합은 \(12\)이다. 1 3 10은 \(3,4,5\)에 각각 \(10\)을 더해 그 합을 \(42\)로, \(1\)번 서브트리 합을 \(45\)로, \(5\)번 서브트리(자기 자신) 합을 \(15\)로 만든다.
1
7
3
2 1
1 1 100
2 1
7
107
정점이 하나뿐이면 그 서브트리는 자기 자신뿐이다. 처음 합은 \(7\), \(100\)을 더하면 \(107\)이 된다.
골드 I막혔나요? 코인으로 단계별 힌트를 잠금 해제하세요 — 첫 힌트는 가벼운 방향 제시, 뒤로 갈수록 더 많이 알려 줍니다. 문제를 풀면 모든 힌트가 무료로 공개됩니다.
riseoj 작성
출처 Original
평가 및 의견
회사 조직도
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
회사 조직도