树上问题(link)
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
【题目描述】
给定一棵无根树,树上有个节点,编号为到,有条无向边,每条边连接两个节点。树上任意两个节点之间都存在唯一路径。
现在指定编号为的节点为根节点,将这棵树变成有根树。树上除了编号为的节点外,每个节点都有唯一的父节点,一个节点可以有多个子节点。
你需要处理次询问,第次询问包含个节点。对于每次询问,你需要确认树上是否存在一条从编号为的节点到某个节点的路径,使得询问的个节点,要么在这条路径上,要么到这条路径上的某个节点的距离为。
注:树上的节点到节点的距离,是指从到的路径所经过的边的数量。
【输入格式】
第一行两个空格隔开的整数和。
接下来行,表示树的结构,每行两个空格隔开的整数和,表示树上有一条边连接编号分别为和的节点。
【输出格式】
输出行,表示每次询问的答案。如果能够找到满足题目要求的路径,则输出"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中,树的结构如下:
[]
第一次询问包含个节点,可以选择1->3->6这条路径,节点和节点在路径上,节点和节点到路径上的节点的距离均为。
第二次询问包含个节点,树上没有满足题目要求的路径。
【数据规模与约定】
对于30%的数据,保证除了编号为的根节点外,其他节点最多只有一个子节点。
另有30%的数据,保证。
对于100%的数据,保证。