蓝桥杯2018年第九届真题-版本分支-题解（Java代码）

解题思路:

这道题用循环去找父节点的父节点肯定会超时，因为他可能会出现只有一个分支的树，这样时间复杂度就变成O（100000×100000）。

首先通过以下语句重新赋值每一个节点的ID，让父节点ID小于子节点ID，ID的映射关系保存到map数组中。

		LinkedList<Integer> queue = new LinkedList<Integer>();
		queue.add(1);
		int node_id = 1;
		map[1] = node_id++;
		while (!queue.isEmpty()) {
			int p = queue.remove();
			int p_id = map[p];
			ArrayList<Integer> children = tree_children[p];
			for (int c : children) {
				map[c] = node_id++;
				tree[map[c]] = p_id;
			}
			queue.addAll(children);
		}

其中 

				tree[map[c]] = p_id;

语句构建ID改变过后的双亲表示法的树。

然后

		for (int i = n; i > 0; --i) {
			if (-1 == to[i]) {
				ArrayList<Integer> line = new ArrayList<Integer>();
				lines.add(line);
				int t = lines.size() - 1;
				int p = i;
				while (0 != p) {
					if (-1 == to[p]) {
						to[p] = t;
						line.add(p);
					} else {
						line.add(-p);
						break;
					}
					p = tree[p];
				}
				if (0 == p) {
					line.add(-Integer.MAX_VALUE);
				}
				Collections.reverse(line);
			}
		}

代码块将树的每一条继承关系保存到一个line中（从最后一个开始向前递归存储，如果遇到已经存储的节点，就把最后一个元素链接到该节点）。因为我们对树的ID按照继承关系进行了重新排列。所以line中的元素是按照大小顺序存储的（可以用二分查找时间复杂度O(100000*log(100000))），并且最后一个元素为为另一条line的索引（如果没有找到，找到父line，继续查找）。

注意事项:
其中

								if (x > link_to)
									break;

语句判断父line中的目标是否在父line的前半部分，如果不是那x就不是父节点就break。
参考代码:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * Hello world!
 */

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int q = sc.nextInt();
		int[] tree = new int[n + 1];
		@SuppressWarnings("unchecked")
		ArrayList<Integer>[] tree_children = new ArrayList[n + 1];
		int[] to = new int[n + 1];
		int[] map = new int[n + 1];
		Arrays.fill(to, -1);
		ArrayList<ArrayList<Integer>> lines = new ArrayList<ArrayList<Integer>>();

		for (int i = 0; i <= n; ++i) {
			tree_children[i] = new ArrayList<Integer>();
		}
		for (int i = 1; i < n; ++i) {
			int u = sc.nextInt();
			int v = sc.nextInt();
//			tree[v] = u;
			tree_children[u].add(v);
		}

		LinkedList<Integer> queue = new LinkedList<Integer>();
		queue.add(1);
		int node_id = 1;
		map[1] = node_id++;
		while (!queue.isEmpty()) {
			int p = queue.remove();
			int p_id = map[p];
			ArrayList<Integer> children = tree_children[p];
			for (int c : children) {
				map[c] = node_id++;
				tree[map[c]] = p_id;
			}
			queue.addAll(children);
		}

//		for (int i = 1; i <= n; ++i) {
//			if (tree[i] >= i) {
//				while (true)
//					;
//			}
//		}

		for (int i = n; i > 0; --i) {
			if (-1 == to[i]) {
				ArrayList<Integer> line = new ArrayList<Integer>();
				lines.add(line);
				int t = lines.size() - 1;
				int p = i;
				while (0 != p) {
					if (-1 == to[p]) {
						to[p] = t;
						line.add(p);
					} else {
						line.add(-p);
						break;
					}
					p = tree[p];
				}
				if (0 == p) {
					line.add(-Integer.MAX_VALUE);
				}
				Collections.reverse(line);
			}
		}

		while (0 < q--) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			x = map[x];
			y = map[y];
////			int p = tree[y];
//			int p = y;
//			while (0 != p && x != p)
//				p = tree[p];
			int t = to[y];
			boolean is_parent = false;
			if (x <= y) {
				ArrayList<Integer> line = lines.get(t);
				for (;;) {
					int idx = Collections.binarySearch(line, x);
					if (idx < 0) {
						if (-2 == idx) {
							int link_to = -line.get(0);
							if (Integer.MAX_VALUE != link_to) {
								if (x > link_to)
									break;
								int next_to = to[link_to];
								line = lines.get(next_to);
							} else
								break;
						} else
							break;
					} else {
						is_parent = true;
						break;
					}

				}
			}

			System.out.println(is_parent ? "YES" : "NO");
		}
		return;
	}
}