축제

난이도: Lv. 5

제출: 78 명

참가자: 31 명

정답률: 70.00 %

지원 언어: C

C++

Java

Python

Rust

로그인 후 문제풀이가 가능합니다.

언어별 시간/메모리

언어별 시간/메모리 표
언어	시간	메모리
C	5초	1024MB
C++	5초	1024MB
Python	15초	1024MB
Java	10초	1024MB
Rust	5초	1024MB

자연을 사랑하는 요정 깐프들은 거대한 나무, 세계수에 산다. 세계수는 $N$ 개의 정점으로 이루어진 트리로 표현할 수 있다. 정점에는 $1$ 에서 $N$ 까지 번호가 붙어 있으며, 처음에 $i$ 번 정점에는 $G_{i}$ 명의 깐프들이 살고 있다.

두 정점은 하나의 가지로 연결되어 있어 깐프들은 가지를 따라 정점 사이를 양방향으로 이동할 수 있다. 가지는 총 $N - 1$ 개 있으며, 임의의 두 정점 사이 이동이 가능하도록 연결되어 있다. 가지에도 $1$ 에서 $N - 1$ 까지의 번호가 붙어 있으며, $i$ 번 가지는 $X_{i}$ 번 정점과 $Y_{i}$ 번 정점을 연결하는 길이가 $L_{i}$ 인 가지이다.

수명이 긴 깐프들에게 앞으로 $Q$ 번의 이벤트가 일어난다. $i$ 번째 이벤트는 다음 2 종류 중 하나와 같다.

$v_{i}$ 번 정점에서 세계수에 사는 모든 깐프들이 모이는 축제를 연다.
$v_{i}$ 번 정점에 새로운 깐프가 $g_{i}$ 명 더 태어나 살게 된다.

1번 종류의 이벤트에서 깐프들은 수가 매우 많기 때문에, 모든 깐프들이 세계수의 가지를 따라 이동하는 과정에서 세계수에 많은 부담이 간다. 하지만 축제에는 모든 깐프가 참여해야 하기에, 어느 정도 부담이 가는지 미리 계산해서 적절히 세계수를 관리하고자 한다.

축제가 일어나 깐프들이 이동할 때, 세계수에 가해지는 부담은 각 정점에 사는 모든 깐프들이 $v_{i}$ 번 정점으로 이동한 거리들의 합으로 계산한다. 깐프들은 세계수에 부담을 최소화하기 위해 자신이 사는 정점에서 다른 정점으로 이동할 때 항상 최단 거리로 이동한다.

추가로 1번 이벤트들은 서로 독립적이다. 따라서 축제를 위해 모인 후 모든 깐프는 자신이 원래 있던 정점으로 돌아간다. 돌아가는 길은 세계수에 부담이 되지 않는다.

이벤트들이 일어난 순서대로 주어질 때, 1번 종류의 이벤트가 주어질 때마다 세계수에 가해지는 부담을 구해 출력하는 프로그램을 작성하라.

제약조건

[문제 제약 조건]
[조건 1] $1 \leq N, Q \leq 6 \times 1 0^{4}$
[조건 2] $1 \leq G_{i} \leq 1 0^{3}$
[조건 3] $1 \leq X_{i}, Y_{i} \leq N$
[조건 4] $1 \leq L_{i} \leq 1 0^{3}$
[조건 5] $1 \leq v_{i} \leq N$
[조건 6] $1 \leq g_{i} \leq 1 0^{3}$

[서브 태스크별 제약 조건]
Subtask1 (10점): $N \leq 4 \times 1 0^{3}$
Subtask2 (30점): 1번 종류의 이벤트만 입력으로 들어온다.
Subtask3 (60점): 다른 제약 조건이 없습니다.

입력형식

첫 번째 줄에 정점의 수를 나타내는 자연수 $N$ 이 주어진다.
두 번째 줄에 각 정점에 사는 깐프의 수를 나타내는 $N$ 개의 자연수 $G_{1}, G_{2}, \dots, G_{N}$ 이 주어진다.
다음 $N - 1$ 개의 줄의 $i$ 번째 줄에는 가지의 정보를 나타내는 세 자연수 $X_{i}, Y_{i}, L_{i}$ 가 주어진다.
다음 줄에는 이벤트의 개수를 나타내는 자연수 $Q$ 가 주어진다.
다음 $Q$ 개의 줄의 $i$ 번째 줄에는 이벤트의 정보를 나타내는 자연수들이 주어진다. 첫 번째 자연수는 $1$ 또는 $2$ 이며, 이는 이벤트의 종류를 나타낸다. $1$ 이 주어진 경우 $v_{i}$ 만, $2$ 만 주어진 경우 $v_{i}, g_{i}$ 가 추가로 주어진다.

출력형식

1번 종류의 이벤트가 주어질 때 마다 각 줄에, 모든 깐프들이 축제가 일어나는 정점으로 이동할 때 세계수에 가해지는 부담을 출력한다.

입력예제1

3 1 1 1 1 2 1 2 3 100 7 1 1 1 2 1 3 2 2 1 1 1 1 2 1 3

출력예제1

102 101 201 103 101 301

입력예제2

6 1 1 1 1 1 1 1 3 1 2 3 10 3 4 100 4 5 1000 4 6 10000 14 1 1 1 2 1 3 1 4 1 5 1 6 2 6 1 2 3 1 1 1 1 2 1 3 1 4 1 5 1 6

출력예제2

11315 11351 11311 11311 15311 51311 21417 21471 21411 21411 27411 61411

소프티어

연습문제

축제