## CEOI '19 P2 - Dynamic Diameter

View as PDF

Points: 25 (partial)
Time limit: 2.5s
Memory limit: 1G

Problem types

You are given a weighted undirected tree on vertices and a list of updates. Each update changes the weight of one edge. The task is to output the diameter of the tree after each update.

(The distance between two vertices is the sum of the weights on the unique simple path that connects them. The diameter is the largest of all those distances.)

#### Input Specification

The first line contains three space-separated integers and – the number of vertices in the tree, the number of updates and the limit on the weights of edges. The vertices are numbered through .

Next, lines describing the initial tree follow. The -th of these lines contains three space-separated integers meaning that initially, there is an edge between vertices and with weight . It is guaranteed that these lines describe a tree.

Finally, lines describing queries follow. The -th of these lines contains two space-separated integers . These two integers are then transformed according to the following scheme:

where is the result of the last query (initially ). Tuple represents a query which takes the -th edge from the input and sets its weight to .

#### Output Specification

Output lines. For each , line should contain the diameter of the tree after the -th update.

#### Scoring

Subtask 3 ( points): and the edges of the tree are exactly all valid edges of the form (Hence, the tree is a star centered at vertex .)

Subtask 4 ( points): , and the edges of the tree are exactly all valid edges of the forms and (Hence, if we were to root the tree at vertex , it would be a balanced binary tree.)

Subtask 5 ( points): it is guaranteed that after each update a longest simple path goes through vertex

#### Sample Input 1

4 3 2000
1 2 100
2 3 1000
2 4 1000
2 1030
1 1020
1 890

#### Sample Output 1

2030
2080
2050

#### Sample Input 2

10 10 10000
1 9 1241
5 6 1630
10 5 1630
2 6 853
10 1 511
5 3 760
8 3 1076
4 10 1483
7 10 40
8 2051
5 6294
5 4168
7 1861
0 5244
6 5156
3 3001
8 5267
5 3102
8 3623

#### Sample Output 2

6164
7812
8385
6737
6738
7205
6641
7062
6581
5155

#### Note

The first sample is depicted in the figure below. The left-most picture shows the initial state of the graph. Each following picture depicts the situation after an update. The weight of the updated edge is painted green, and the diameter is red.

The first query changes the weight of the 3rd edge, i.e. , to . The largest distance between any pair of vertices is – the distance between and .

As the answer is , the second query is

Hence the weight of the edge is changed to . This causes the pair to be the pair with the greatest distance, namely .

The third query is decoded as

As the weight of the edge decreases to , the most distant pair is suddenly with .