java实现第九届蓝桥杯版本分支

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.BufferedInputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.*;public class MainB {public static InputReader in = new InputReader(new BufferedInputStream(System.in));public static PrintWriter out = new PrintWriter(System.out);public static int n, q, u, v, x, y;public static ArrayList<Integer>[] child = new ArrayList[100010];public static ArrayList<Integer>[] next = new ArrayList[100010];public static void main(String[] args) {n = in.nextInt();q = in.nextInt();for (int i = 1; i <= n; i++) {next[i] = new ArrayList<>();child[i] = new ArrayList<>();}for (int i = 1; i < n; i++) {u = in.nextInt();v = in.nextInt();next[u].add(v);}child[1] = getChild(1);while (q-- > 0) {x &#Int();y = in.nextInt();if (child[x].contains(y)) {out.println("YES");out.flush();} else {out.println("NO");out.flush();}}out.close();}static ArrayList<Integer> getChild(int root) {int len = next[root].size();for (int i = 0; i < len; i++)child[root].addAll(getChild(next[root].get(i)));child[root].add(root);return child[root];}static class InputReader {public BufferedReader reader;public StringTokenizer tokenizer;public InputReader(InputStream stream) {reader = new BufferedReader(new InputStreamReader(stream), 32768);tokenizer = null;}public String next() {while (tokenizer == null || !tokenizer.hasMoreTokens()) {try {tokenizer = new adLine());} catch (IOException e) {throw new RuntimeException(e);}}Token();}public String nextLine() {String str = null;try {str = adLine();} catch (IOException e) {e.printStackTrace();}return str;}public int nextInt() {return Integer.parseInt(next());}public long nextLong() {return Long.parseLong(next());}public Double nextDouble() {return Double.parseDouble(next());}public BigInteger nextBigInteger() {return new BigInteger(next());}}
}