题目描述
给一棵有根树，以及一些询问，每次询问树上的2 个节点A、B，求它们的最近公共祖先.

输入

第一行一个整数N.接下来N 个数，第i 个数Fi 表示i 的父亲是Fi. 若Fi = 0,则i 为树根.
接下来一个整数M.接下来M 行，每行2 个整数A、B，询问节点(A xor LastAns)、(Bxor LastAns)的最近公共祖先. 其中LastAns 为上一个询问的答案，一开始LastAns = 0.
输出
对每一个询问输出相应的答案.

样例输入
10
0 1 2 3 2 4 2 5 4 9
10
3 9
2 7
7 8
1 1
0 6
6 11
6 3
10 7
2 15
7 7
样例输出
3
1
4
5
2
4
2
5
2
5

#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int maxn = 5e5 + 5;
vector<int>map[maxn];
int vis[maxn];
int fa[maxn];
int Size[maxn];
int Mainson[maxn];
int depth[maxn];
int root;

void DFS1(int v)
{
	vis[v] = 1; Size[v] = 1;
	for (int i = 0; i < map[v].size(); i++) {
		int u = map[v][i];
		if (!vis[u]) {
			fa[u] = v;
			depth[u] = depth[v] + 1;
			DFS1(u);
			Size[v] += Size[u];
			if (Size[u] > Size[Mainson[v]])Mainson[v] = u;
		}
	}
}

int path[maxn];
void DFS2(int u)
{
	vis[u] = 1;
	for (int i = 0; i < map[u].size(); i++) {
		int v = map[u][i];
		if (!vis[v]) {
			if (v == Mainson[u])path[v] = path[u];
			else path[v] = v;
			DFS2(v);
		}
	}
}

int lca(int a, int b)
{
	while (path[a] != path[b]) {
		if (depth[path[a]] > depth[path[b]])a = fa[path[a]];
		else b = fa[path[b]];
	}
	return depth[a] < depth[b] ? a : b;
}
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int a; scanf("%d", &a);
		if (a == 0)root = i;
		else {
			map[i].push_back(a); map[a].push_back(i);
		}
	}
	memset(vis, 0, sizeof(vis)); depth[root] = 0;
	DFS1(root);
	memset(vis, 0, sizeof(vis)); path[root] = root;
	DFS2(root);
	int m;scanf("%d", &m);
	int lastans = 0;
	//for (int i = 1; i <= n; i++)printf("%d\n", depth[i]);
	for (int i = 1; i <= m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		int ans = lca(a ^ lastans, b ^ lastans);
		printf("%d\n", ans);
		lastans = ans;
	}
}