求助树论题【悬关】
  • 板块学术版
  • 楼主封禁用户
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/11/9 21:08
  • 上次更新2023/11/9 22:47:52
查看原帖
求助树论题【悬关】
1056908
封禁用户楼主2023/11/9 21:08

题目描述:

你被邪恶的Van东东抓住了,他把你困在一个地牢里面让你锻炼♂身体。 地牢可以看做一棵有 nn 个节点的树,树的根为 11,每条边的长度都是 11
他每天要让你玩♂跑步,你每天要跑的路程是树上最长的路径的长度

不幸的是,每天地牢都可能有一些子树被损坏,被损坏的点就不能到达了。(可能出现被破坏子树包含的情况)
Van东东会在当天晚上用Dark力量修好它,但是当天这些点都不能用了。

更不幸的是,他还是会让你跑一条没有被损坏的最长路径,你必须服从 master 的指令

现在你得知了未来 mm 天的子树损坏情况,对于每一天,你需要求出当天的跑步距离

输入格式:

第一行两个数 n,mn,m 表示地牢的节点数和未来的天数
接下来 n−1n−1 行,每行两个数 x,yx,y 表示地牢里有一条 x−yx−y 的边
接下来 mm 行,每行第一个数为 kik_i 表示当天损坏的子树个数
改行接下来 kik_i 个数 aja_j 表示当天被损坏的子树根节点编号

1≤n,m≤2×105,∑ki≤5×105,0≤ki≤n1\le n,m\le2×10^5,\sum k_i\le5×10^5 ,0\le k_i\le n

输出格式:

共 mm 行,第 ii 行输出表示未来第 ii 天的跑动距离

样例

样例输入:

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

样例输出:

6
5
3
0
3
5
6







求代码

2023/11/9 21:08
加载中...