题目描述

You are given a tree with $n$ nodes numbered from $1$ to $n$ and $n - 1$ edges. Each node has a color. Initially, all of them are white.

We are going to perform $q$ operations. In each operation, two vertices $u$ and $v$ will be given, and we will color black to the points along the simple path from $u$ to $v$ ($u,v$ inclusive). Note that a simple path in the tree is defined as a path that does not pass through any vertex more than once.

After each operation, you are required to determine the length of the longest simple path in the tree where all nodes on the path are the same color. The length of a path is defined as the number of nodes on the path.

输入格式

The first line contains a single integer $T$ ($1 \le T \le 100$) indicating the number of test cases.

For each test case, the first line contains two integers $n$ ($1 \le n \le 2\times 10^5$) and $q$ ($1 \le q \le 2\times 10^5$), indicating the number of nodes in the tree and the number of operations, respectively.

In the following $n-1$ lines, each contains two integers $u$ and $v$, representing an edge from vertex $u$ to $v$ in the tree.

Then follow $q$ lines, each contains two integers $u$ and $v$, representing an operation that colors black to the points along the path from vertex $u$ to $v$.

It is guaranteed that the sum of $n$ and $q$ of all the test cases in a test does not exceed $2\times 10^5$ respectively.

输出格式

For each test case, output $q$ lines, each line should contain an integer representing the length of the longest simple path in the tree where all nodes on the path are the same color after the corresponding operation.

题目大意

题目描述

给你一棵有 $n$ 个节点的树，节点编号从 $1$ 到 $n$，并且有 $n-1$ 条边。每个节点都有一个颜色。起初，所有节点的颜色都是白色。

我们将进行 $q$ 次操作。在每次操作中，会给出两个顶点 $u$ 和 $v$，然后我们将沿着从 $u$ 到 $v$ 的简单路径上的所有节点（包括 $u$ 和 $v$）染成黑色。注意，树中的简单路径定义为路径上的任意顶点都不会被重复经过。

在每次操作之后，你需要确定树中最长的简单路径，其路径上的所有节点的颜色相同。路径的长度定义为路径上的节点数目。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数 $n$ ($1 \le n \le 2\times 10^5$) 和 $q$ ($1 \le q \le 2\times 10^5$)，分别表示树中节点的数量和操作的数量。

紧接着$^{(1)}$的 $n-1$ 行中，每行包含两个整数 $u$ 和 $v$，表示树中顶点 $u$ 和 $v$ 之间的一条边。

接下来 $q$ 行，每行包含两个整数 $u$ 和 $v$，表示将从顶点 $u$ 到顶点 $v$ 的路径上的所有节点染成黑色的操作。

保证一个测试中所有测试用例的 $n$ 和 $q$ 的总和均不超过 $2\times 10^5$。$^{(2)}$

注释：

• (1):也可以译为接下来，此处译者只是想区分下条的语句。
• (2)可以用以下数学表达式表示：

$$\sum_{i=1}^{T} n_i \leq 2 \times 10^5 \quad \text{且} \quad \sum_{i=1}^{T} q_i \leq 2 \times 10^5 $$

其中 $n_i$ 和 $q_i$ 分别表示第 $i$ 个测试用例中的节点数量和操作数量。

输出格式

对于每个测试用例，输出 $q$ 行，每行应包含一个整数，表示在执行相应操作后，树中所有节点颜色相同的最长简单路径的长度。

翻译者：Immunoglobules

1
8 6
1 2
1 3
2 4
4 5
2 6
4 8
3 7
4 8
7 7
4 5
2 2
4 6
5 1

5
4
4
3
4
4