← 返回题目列表

Codeforces · 1904/E

E. 树查询

中文机器翻译题面 查看原题

由于 Hayate 没有从圣诞老人那里得到任何圣诞礼物,所以他只能解决树查询问题。

Hayate 有一个包含 $$$n$$$ 节点的树。

Hayate 现在希望您回答 $$$q$$$ 查询。每个查询由一个节点 $$$x$$$ 和 $$$k$$$ 其他附加节点 $$$a_1,a_2,\ldots,a_k$$$ 组成。这些 $$$k+1$$$ 节点保证都是不同的。

对于每个查询,您必须在删除节点 $$$a_1,a_2,\ldots,a_k$$$ 以及连接到至少一个节点 $$$a_1,a_2,\ldots,a_k$$$ 的所有边后找到从节点 $$$x^\dagger$$$ 开始的最长简单路径的长度。

$$$^\dagger$$$ 从节点 $$$x$$$ 开始的长度为 $$$k$$$ 的简单路径是一系列不同的节点 $$$x=u_0,u_1,\ldots,u_k$$$,使得节点 $$$u_{i-1}$$$ 和 $$$u_i$$$ 之间存在一条边,对于所有 $$$1 \leq i \leq k$$$。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) - 树的节点数和查询数。

以下 $$$n - 1$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$) - 表示节点 $$$u$$$ 和 $$$v$$$ 之间的边。保证给定的边形成一棵树。

以下 $$$q$$$ 行描述了查询。每行包含整数 $$$x$$$、$$$k$$$ 和 $$$a_1,a_2,\ldots,a_k$$$ ($$$1 \leq x \leq n$$$, $$$0 \leq k < n$$$, $$$1 \leq a_i \leq n$$$) — 起始节点、已删除节点的数量和已删除节点。

保证对于每个查询,$$$x,a_1,a_2,\ldots,a_k$$$ 都是不同的。

保证所有查询的 $$$k$$$ 总和不会超过 $$$2 \cdot 10^5$$$。

输出

对于每个查询,输出一个整数表示该查询的答案。

示例

输入 #1

7 7
1 2
1 3
3 4
2 5
2 6
6 7
2 0
2 1 1
2 2 1 6
3 1 4
3 1 1
5 0
5 2 1 6

输出 #1

3
2
1
4
1
4
1

输入 #2

4 4
1 2
1 3
2 4
2 1 3
3 1 4
2 1 4
2 3 1 3 4

输出 #2

1
2
2
0

注意

第一个例子中,树如下:

在第一个查询中,没有丢失任何节点。从节点 $$$2$$$ 开始的最长简单路径是 $$$2 \to 1 \to 3 \to 4$$$。因此,答案是$$$3$$$。

在第三个查询中,节点 $$$1$$$ 和 $$$6$$$ 丢失,树如下所示。从节点 $$$2$$$ 开始的最长简单路径是 $$$2 \to 5$$$。因此,答案是$$$1$$$。