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 =in.nextInt();

            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 StringTokenizer(reader.readLine());

                } catch (IOException e) {

                    throw new RuntimeException(e);

                }

            }

            return tokenizer.nextToken();

        }

        public String nextLine() {

            String str = null;

            try {

                str = reader.readLine();

            } 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());

        }

    }

}

巴特西

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

最新文章

热门文章