版本分支第九届蓝桥杯国赛真题第五题 java

71 阅读 0 评论 47 点赞

我是靠谱客的博主强健鸭子，最近开发中收集的这篇文章主要介绍版本分支第九届蓝桥杯国赛真题第五题 java，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

标题：版本分支

小明负责维护公司一个奇怪的项目。这个项目的代码一直在不断分支(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

资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入…” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。

解题思路：直接递归肯定会超时，所以采用递归一次记录所有节点的儿子，之后每次只需对比即可。


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;
public class BanBenFenZhi {
public static ArrayList<Integer>[] child = new ArrayList[100010];//细节
public static ArrayList<Integer>[] next = new ArrayList[100010];
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String[] s=br.readLine().split(" ");
int n=Integer.parseInt(s[0]);
int q=Integer.parseInt(s[1]);
int[] a=new int[n+1];
for (int i = 1; i <= n; i++) {
next[i] = new ArrayList<>();//细节
child[i] = new ArrayList<>();
}
for (int i = 0; i < n-1; i++) {
s=br.readLine().split(" ");
int u=Integer.parseInt(s[0]);
int v=Integer.parseInt(s[1]);
//System.out.println(u+" "+v);
//a[v]=u;
next[u].add(v);
}
child[1] = getChild(1);
while (q-- > 0) {
s=br.readLine().split(" ");
int x =Integer.parseInt(s[0]);
int y =Integer.parseInt(s[1]);
if (child[x].contains(y)) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
static ArrayList<Integer> getChild(int root) {
int len=next[root].size();
for (int i = 0; i < len; i++) {
//获取其儿子节点并添加到ArraryList数组中
child[root].addAll(getChild(next[root].get(i)));
}
child[root].add(root);
return child[root];
}
}