왕도의 보급로
플래티넘 I의견: 0
수도를 뿌리로 하는 \(N\)개의 도시가 \(N-1\)개의 도로로 연결되어 트리를 이룬다. 각 도시에는 비축된 보급량이 있으며, 처음에는 모두 \(0\)이다.
다음 두 종류의 작업이 \(Q\)번 주어진다.
1 u v x : 도시 \(u\)와 \(v\)를 잇는 경로 위의 모든 도시(양 끝 포함)에 보급량을 \(x\)만큼 더한다.
2 u v : 도시 \(u\)와 \(v\)를 잇는 경로 위의 모든 도시의 보급량 합을 출력한다.
도시 수와 작업 수가 매우 크므로 경로를 직접 따라가는 풀이는 통과할 수 없다.
\(1 \le N \le 100{,}000\)
\(1 \le Q \le 100{,}000\)
\(1 \le u, v, a, b \le N\)
\(1 \le x \le 10^4\)
첫 줄에 도시 수 \(N\)과 작업 수 \(Q\)가 주어진다.
다음 \(N-1\)개의 줄에 도로의 양 끝 도시 번호 \(a\), \(b\)가 주어진다.
이어서 \(Q\)개의 줄에 위 형식의 작업이 하나씩 주어진다. 갱신 작업은 1 u v x, 질의 작업은 2 u v 형식이다.
각 질의 작업(2번)에 대해 경로 위 보급량의 합을 한 줄에 하나씩 출력한다.
5 4
1 2
1 3
3 4
3 5
1 2 4 5
2 1 4
1 5 5 3
2 2 5
15
18경로 2-1-3-4에 모두 5를 더한다(도시 1,2,3,4 = 5, 도시 5 = 0). 질의 1-4 경로(1,3,4)의 합은 \(5+5+5=15\). 이어 도시 5에 3을 더하면 도시 5 = 3. 질의 2-5 경로(2-1-3-5)의 합은 \(5+5+5+3=18\).
4 4
1 2
2 3
3 4
1 1 4 2
2 2 3
1 2 2 10
2 1 4
4
18사슬 1-2-3-4 전체에 2를 더하면 각 도시 = 2. 질의 2-3의 합은 \(2+2=4\). 도시 2에 10을 더하면 도시 2 = 12. 질의 1-4의 합은 \(2+12+2+2=18\).
riseoj 작성
출처 Original
평가 및 의견
왕도의 보급로
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
왕도의 보급로