405419: GYM101955 D Diameter of a Tree

Given a weighted tree $$$T_0$$$, we define its diameter as the length of the longest path between two vertices on it, where the length of a path is equal to the sum of weights of edges in the path.

If the tree stretches like a spider or a yawning tiger, its diameter will change. Let's use $$$T_i$$$ to denote the state of the tree after $$$i$$$ seconds, at which time the weight of each edge has been increased by exactly $$$i$$$ units from $$$T_0$$$.

You will be presented with several different queries, and you should calculate the tree's diameter at some specified time for each query.

The input contains several test cases, and the first line contains a positive integer $$$T$$$ indicating the number of test cases which is up to $$$60$$$.

For each test case, the first line contains two integers $$$n$$$ and $$$m$$$ indicating the number of vertices in the tree and the number of given queries respectively, where $$$2 \le n \le 2 \times 10^5$$$ and $$$1 \le m \le 2 \times 10^5$$$.

Each of the following $$$(n - 1)$$$ lines contains three integers $$$u, v$$$ and $$$w$$$ which represent an edge in the original tree between the $$$u$$$-th vertex and the $$$v$$$-th one of weight $$$w$$$, where $$$1 \le u, v \le n$$$, $$$u \ne v$$$ and $$$1 \le w \le 10^8$$$.

Each of the following $$$m$$$ lines describes a query containing only one integer $$$k$$$ that asks you to calculate the diameter of the tree $$$T_k$$$, where $$$0 \le k \le 10^9$$$.

We guarantee that the sum of $$$n$$$ in all test cases is no larger than $$$10^6$$$, and the sum of $$$m$$$ in all test cases is no larger than $$$10^6$$$ as well.

For each test case, output a line containing "Case #x:" (without quotes) at first, where x is the test case number starting from $$$1$$$.

Then output $$$m$$$ lines corresponding to all queries. The $$$i$$$-th line of them contains an integer indicating the answer to the $$$i$$$-th query.

2
3 3
1 2 1
1 3 5
5
10
100
5 6
1 2 100
2 3 5
2 4 1
4 5 1
0
1
2
3
4
5

Case #1:
16
26
206
Case #2:
105
107
109
111
114
117

In the second sample case:

• the diameter of $$$T_0$$$ is $$$105$$$, which is the length of the path $$$1 - 2 - 3$$$; and
• the diameter of $$$T_5$$$ is $$$117$$$, which is the length of the path $$$1 - 2 - 4 - 5$$$.