#C. 树上问题(link)

    传统题 1000ms 256MiB

树上问题(link)

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

【题目描述】

给定一棵无根树,树上有nn个节点,编号为11nn,有n1n-1条无向边,每条边连接两个节点。树上任意两个节点之间都存在唯一路径。

现在指定编号为11的节点为根节点,将这棵树变成有根树。树上除了编号为11的节点外,每个节点都有唯一的父节点,一个节点可以有多个子节点。

你需要处理mm次询问,第ii次询问包含kik_i个节点。对于每次询问,你需要确认树上是否存在一条从编号为11的节点到某个节点xx的路径,使得询问的kik_i个节点,要么在这条路径上,要么到这条路径上的某个节点的距离为11

注:树上的节点uu到节点vv的距离,是指从uuvv的路径所经过的边的数量。

【输入格式】

第一行两个空格隔开的整数nnmm

接下来n1n-1行,表示树的结构,每行两个空格隔开的整数uuvv,表示树上有一条边连接编号分别为uuvv的节点。

【输出格式】

输出mm行,表示每次询问的答案。如果能够找到满足题目要求的路径,则输出"YES",否则输出"NO"(不包含引号)。

7 2
1 2
1 3
1 4
5 2
6 3
7 4
4 2 4 3 6
3 5 6 7
YES
NO
10 6
1 2
1 3
1 4
2 5
2 6
3 7
7 8
7 9
9 10
4 3 8 9 10
3 2 4 6
3 2 1 5
3 4 8 2
2 6 10
3 5 4 7
YES
YES
YES
YES
NO
NO

【样例解释】

在样例1中,树的结构如下:

[fuo8W4.png]

第一次询问包含44个节点2,3,4,62,3,4,6,可以选择1->3->6这条路径,节点33和节点66在路径上,节点44和节点22到路径上的节点11的距离均为11

第二次询问包含33个节点5,6,75,6,7,树上没有满足题目要求的路径。

【数据规模与约定】

对于30%的数据,保证除了编号为11的根节点外,其他节点最多只有一个子节点。

另有30%的数据,保证n10,m10,ki10(1im)n\le 10,m\le 10,k_i \le 10(1\le i \le m)

对于100%的数据,保证n200,m200,ki200(1im)n \le 200,m \le 200, k_i \le 200(1\le i \le m)

CSP-J 模拟测试Ⅱ

未参加
状态
已结束
规则
OI
题目
4
开始于
2021-8-14 14:00
结束于
2021-8-14 17:30
持续时间
3.5 小时
主持人
参赛人数
81