시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB3115947.368%

문제

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

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

현재, $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$로 변화했다는 것을 의미한다.

출력

첫 줄에는 현재 교통량을 토대로 구할 수 있는 BOJ 나라의 총 유동 차량 수로 가능한 최댓값을 출력한다.

다음 $Q$ 개의 줄의 각 줄에는, 교통량이 변화할 때 마다 변화한 교통량을 토대로 구할 수 있는 BOJ 나라의 총 유동 차량 수로 가능한 최댓값을 출력한다.

제한

  • $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$)
  • 입력으로 주어지는 모든 수는 정수다.

예제 입력 1

4 1
1 2 5
2 3 4
3 4 8
3 2

예제 출력 1

13
7

교통량이 변화하기 전, 가능한 유동차량 수의 배치를 생각하면, 1번 도시에 3, 2번 도시에 2, 3번 도시에 2, 4번 도시에 6으로 유동차량 수를 배치했을 때, 합이 13으로 최대가 된다. 이보다 총합이 더 크면서 조건을 만족하는 배치는 존재하지 않는다.

3번 도로의 교통량이 2로 변화한 후에는, 1번 도시에 2, 2번 도시에 3, 3번 도시에 1, 4번 도시에 1으로 유동차량 수를 배치했을 대, 합이 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

예제 출력 2

3086544
3159775
3316754
3062659
2502436
2111693
1673626
1641079
1956877
1956877
1239206

출처

Contest > BOJ User Contest > Good Bye, BOJ > Hello, BOJ 2022! F번