교통량 분석

시간 제한3초메모리 제한1024 MB

요약

간선마다 양 끝 도시 흐름의 합이 그 간선의 교통량을 넘지 않을 때 모든 도시 흐름 합의 최댓값을 구하고, 교통량이 바뀔 때마다 다시 구합니다.

난이도: 보통10점 중 7점
유형: 트리, 동적 계획법, 세그먼트 트리
정답자: 아직 제출이 없습니다

문제

나라에는 1번부터 $N$ 번까지 번호가 붙은 $N$ 개의 도시가 있다. 또한 서로 다른 두 도시를 잇는 1번부터 $N-1$ 번까지 번호가 붙은 $N-1$ 개의 도로가 있다. 임의의 서로 다른 두 도시는 도로들을 통해 이동할 수 있다. 다시 말해 이 나라의 교통망은 트리 구조이다.

현대 오토에버에 새로 입사한 선재는 도시별 유동 차량 수와 도로별 교통량을 분석해 최적화된 교통정보를 제공하는 과제를 맡았다. 분석 결과에 따르면 각 도시의 유동 차량 수와 각 도로의 교통량은 음이 아닌 정수로 나타낼 수 있다. 또한 각 도로의 교통량은 그 도로가 잇는 두 도시의 유동 차량 수의 합보다 같거나 크다.

현재 $i$ 번 도로의 교통량은 $A_i$ 이다. 선재는 모든 도시의 유동 차량 수 합의 최댓값을 계산해 사용자에게 제공하려 한다. 그런데 차세대 GIS를 개발하는 현대 오토에버는 교통량이 바뀔 때마다 이 값을 실시간으로 다시 계산하기로 했다.

선재는 혼자서도 문제를 해결할 능력이 충분하지만, 입사 동기인 당신에게 도움을 요청했다. 선재와 함께 과제를 해결해 보자.

입력

첫 번째 줄에 도시의 수 $N$ 과 교통량이 변화한 횟수 $Q$ 가 공백으로 구분되어 주어진다.

두 번째 줄부터 $N-1$ 개의 줄 중 $i$ 번째 줄에는 $i$ 번 도로가 잇는 두 도시의 번호 $x_i$ , $y_i$ 와 현재 $i$ 번 도로의 교통량 $A_i$ 가 공백으로 구분되어 주어진다.

$N+1$ 번째 줄부터 $Q$ 개의 줄 중 $i$ 번째 줄에는 교통량이 변화한 도로의 번호 $k_i$ 와 변화한 교통량 $v_i$ 가 공백으로 구분되어 주어진다. 이는 $k_i$ 번 도로의 교통량이 $v_i$ 로 바뀌었다는 뜻이다.

출력

첫 줄에는 현재 교통량을 바탕으로 구할 수 있는 총 유동 차량 수의 가능한 최댓값을 출력한다.

다음 $Q$ 개의 줄에는 교통량이 바뀔 때마다 바뀐 교통량을 바탕으로 구할 수 있는 총 유동 차량 수의 가능한 최댓값을 각 줄에 출력한다.

제한

$2 \leq N \leq 100\,000$
$1 \leq Q \leq 100\,000$
$1 \leq x_i, y_i \leq N$ ( $1 \leq i \leq N-1$ )
임의의 서로 다른 두 도시는 도로들을 통해 이동할 수 있다.
$0 \leq A_i \leq 10^9$ ( $1 \leq i \leq N-1$ )
$1 \leq k_i < N$ ( $1 \leq i \leq Q$ )
$0 \leq v_i \leq 10^9$ ( $1 \leq i \leq Q$ )
입력으로 주어지는 모든 수는 정수다.

예제2

예제 1
입력
```
4 1
1 2 5
2 3 4
3 4 8
3 2
```
예상 출력
```
13
7
```

예제 2

입력

10 10
1 2 328132
2 3 724053
1 4 456768
3 5 601947
4 6 652072
3 7 968719
4 8 89024
5 9 516739
7 10 898630
8 589970
1 485111
9 644535
8 29747
9 253792
4 163880
1 452564
5 967870
6 916369
5 250199

예상 출력