New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

1400: [蓝桥杯2018决赛]版本分支

内存限制：256 MB 时间限制：1 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：690 通过：77
提交提交记录统计

题目描述

小明负责维护公司一个奇怪的项目。这个项目的代码一直在不断分支(branch)但是从未发生过合并(merge)。
现在这个项目的代码一共有N个版本，编号1~N，其中1号版本是最初的版本。
除了1号版本之外，其他版本的代码都恰好有一个直接的父版本；即这N个版本形成了一棵以1为根的树形结构。  
如下图就是一个可能的版本树：
    1
   / \
  2   3
  |  / \
  5 4   6
现在小明需要经常检查版本x是不是版本y的祖先版本。你能帮助小明吗？

输入格式

第一行包含两个整数N和Q，代表版本总数和查询总数。  
以下N-1行，每行包含2个整数u和v，代表版本u是版本v的直接父版本。  
再之后Q行，每行包含2个整数x和y，代表询问版本x是不是版本y的祖先版本。  
对于30%的数据，1 <= N <= 1000  1 <= Q <= 1000  
对于100%的数据，1 <= N <= 100000  1 <= Q <= 100000 

输出格式

对于每个询问，输出YES或NO代表x是否是y的祖先。  

输入样例 复制 

6 5
1 2
1 3
2 5
3 6
3 4
1 1
1 4
2 6
5 2
6 4

输出样例 复制 

YES
YES
NO
NO
NO