트리와 쿼리 21

BOJ 27974 · 시간 제한 5초 · 메모리 제한 1024 MB

$N$ 개의 정점으로 이루어진 트리가 있다. 정점은 $0$번부터 $N-1$ 번까지 번호가 매겨져 있다. 간선에는 음이 아닌 정수 가중치가 매겨져 있다.

다음과 같은 쿼리를 수행해야 한다.

• 1 u v w x: $u$ 와 $v$ 를 잇는 간선을 제거하고, $v$ 와 $w$ 를 잇는 가중치 $x$ 의 간선을 추가한다. $u$ 와 $v$ 를 잇는 간선이 존재함이 보장된다. 연산을 진행한 이후 그래프가 여전히 트리임이 보장된다. ($0 \le x \le 100\,000$)
• 2 k x_1 x_2 ... x_k: 정점 $x_1, x_2, \ldots, x_k$ 에 대해서, 모든 $1 \le i < j \le k$ 에 대해 $x_i$ 와 $x_j$ 를 잇는 유일한 단순 경로를 생각해 보자. 이 단순 경로를 이루는 간선의 합집합에 포함되는 모든 간선의 가중치 합을 출력해야 한다. 모든 $x_i$ 는 서로 다르다. ($1 \le k \le n$)

입력

첫째 줄에 트리의 크기 $N$이 주어진다. ($2 \le N \le 100{,}000$)

다음 $N-1$ 개의 줄에 세 정수 $u, v, w$ 가 주어진다. 두 정점 $u, v$를 잇는 가중치 $w$의 간선이 존재함을 뜻한다. ($0 \le u, v \le N - 1$, $0 \le w \le 100{,}000$)

다음 줄에 쿼리의 개수 $Q$가 주어진다. ($1 \le Q \le 100{,}000$)

다음 $Q$개의 줄에 위에서 설명한 것과 같은 쿼리가 주어진다.

$2$번 쿼리의 $k$ 의 합은 $1$ 이상 $100{,}000$ 이하이다.

출력

$2$번 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1

7
0 1 1
0 2 2
1 3 3
1 4 4
2 5 5
2 6 6
4
1 1 4 5 7
2 3 0 4 6
1 0 2 1 8
2 3 0 4 6

예제 출력 1

20
27