Traffic Analysis

Time limit3sMemory limit1024 MB

Summary

Given a tree whose edges carry traffic volumes, find the maximum total city flow where each edge's endpoints sum to at most its volume, and recompute after each change.

Level: Medium7 of 10
Topics: Tree, Dynamic programming, Segment tree
Solved: No attempts yet

Problem

The country has $N$ cities numbered 1 to $N$ . There are also $N-1$ roads numbered 1 to $N-1$ , each connecting two different cities. Any two cities can reach each other through the roads, so the road network is a tree.

Seon-jae, who has just joined Hyundai Autoever, is tasked with analyzing the traffic flow of each city and the traffic volume of each road to provide optimized traffic information. According to the analysis, the traffic flow of each city and the traffic volume of each road can be expressed as non-negative integers. Also, the traffic volume of each road is at least the sum of the traffic flows of the two cities it connects.

The traffic volume of road $i$ is currently $A_i$ . Seon-jae wants to compute the maximum possible total traffic flow over all cities and provide it to users. However, Hyundai Autoever, which is developing the next-generation GIS, has decided to recompute this value in real time whenever traffic volumes change.

Seon-jae could solve this alone, but he asks you, his new colleague, for help. Solve the task together with him.

Input

The first line contains the number of cities $N$ and the number of traffic volume changes $Q$ , separated by a space.

The next $N-1$ lines are given in order. On line $i$ , there are the two city numbers $x_i$ and $y_i$ connected by road $i$ , and the current traffic volume $A_i$ of road $i$ , separated by spaces.

The next $Q$ lines are given in order. On line $i$ , there are the road number $k_i$ whose traffic volume changed and the new traffic volume $v_i$ , separated by a space. This means the traffic volume of road $k_i$ has changed to $v_i$ .

Output

On the first line, print the maximum possible total traffic flow of all cities that can be obtained from the current traffic volumes.

On each of the next $Q$ lines, print the maximum possible total traffic flow that can be obtained from the traffic volumes after each change.

Constraints

$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$ )
Any two different cities can be reached from each other through the roads.
$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$ )
All numbers in the input are integers.

Examples2

Example 1
Input
```
4 1
1 2 5
2 3 4
3 4 8
3 2
```
Expected output
```
13
7
```

Example 2

Input

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

Expected output