Background

The arcades in Fusu’s city jointly hosted KING of PerforPandora!

However, because heavy snow blocked the roads, some arcades cannot be reached. She wants to know, among the arcades that can reach each other, what the maximum possible distance is.

Problem Description

You are given a tree with $n$ nodes. A tree is defined as an undirected connected graph with $n$ vertices and $n - 1$ edges. The edges of this tree have weights. The distance $\mathrm{dist}(u,v)$ between two nodes $u, v$ is defined as the sum of edge weights along the simple path from $u$ to $v$. It can be proven that the simple path between any two nodes in a tree is unique. In particular, we define $\mathrm{dist}(u, u) = 0$.

Now there are $q$ operations. In each operation, one edge of the tree is deleted. Obviously, after performing at least one operation, the tree will be split into several connected components. After each operation, you need to find the maximum, over all connected components, of the distance between the farthest two nodes within that component.

Formally, after each operation, you need to compute

$$\max\limits_{c \in C}\{\max\limits_{u, v \in c} \mathrm{dist}(u,v)\}$$

where $C$ denotes the set of all current connected components.

Input Format

This problem contains multiple test cases within a single input file. The first line contains a positive integer $T$, denoting the number of test cases. For each test case:

The first line contains two integers $n, q$ ($1 \leq q < n \leq 10^5$), representing the number of nodes in the tree and the number of operations.
The next $n - 1$ lines each contain three integers $u, v, w$ ($1 \leq u, v \leq n$, $1 \leq w \leq 10^5$), indicating an edge between $u$ and $v$ with weight $w$.
The next $q$ lines each contain one integer $e_i$ ($1 \leq e_i < n$), indicating that this operation deletes the $e_i$-th edge in the input. It is guaranteed that each edge is deleted at most once.

It is guaranteed that, within a single test file, the sum of all $n$ does not exceed $3 \times 10^5$.

Output Format

For each test case, output $q$ lines. Each line contains one integer, in order, representing the required answer after each operation.

2
4 2
1 2 1
2 3 2
3 4 3
2
3
12 2
1 2 1
2 3 1
1 4 3
2 5 4
5 6 3
5 7 2
7 8 1
8 9 1
9 10 1
7 11 5
8 12 3
4
6

3
1
10
9

Hint

Hint

Please note that large-scale input and output can significantly affect program performance. Choose appropriate I/O methods, do not flush the output buffer frequently, and avoid TLE.

Translated by ChatGPT 5