时间戳
这就是树上查询问题 ， 是求两个点有什么关系
让我们来看一下样例解释：
注意字母旁边的数字就是时间戳， a在先序遍历（遍历顺序 ： 左，右，根）是第一个进， 第十六个出。
在时间戳里只要一个数比另一个数先进， 后出， 就是另一个数的祖先。
题解:
- 对整棵树进行DFS。对每个点u记住dfs函数进入u的时间TI(u)以及离开u的时间TO(u)，如上图所示，每个节点左边是其dfs进入时间，右边是离开的时间。
- 可以常数时间确定u是不是v的祖先，如果u的进入时间早于v且u的离开时间晚于v，则u是v的祖先：TI(u)<TI(v)<TO(v)<TO(u)，建议读者验证上图中每一对u和v的时间戳。
- 预处理O(n)，每个查询的处理时间O(1)。
代码:
// LOJ10135 祖孙询问
#include <bits/stdc++.h>
const int NN = 4e4 + 4; // 定义常量 NN，表示最大可能的节点数加上一个小的常数
using namespace std;
vector<int> G[NN]; // G数组存储每个节点的子节点，用邻接表的形式表示图
// N为总节点数，TI和TO分别记录每个节点的进入和离开时间戳
int N, TI[NN], TO[NN], timer = 0;
// 深度优先搜索函数，用于遍历树并记录时间戳,
// u为当前节点，fa为父节点，-1表示无父节点
void dfs(int u, int fa = -1) {
TI[u] = ++timer; // 记录其进入时间戳
for (int v : G[u]) // 遍历当前节点u的所有子节点v
if (v != fa) dfs(v, u); // 如果v不是u的父节点，则递归调用dfs
TO[u] = ++timer; // 遍历u的所有子树后，记录其离开时间戳
}
// 如果u的进入时间早于v且u的离开时间晚于v，则u是v的祖先
bool isAncestor(int u, int v) { return TI[u] < TI[v] && TO[v] < TO[u]; }
int solve(int u, int v) {
if (isAncestor(u, v)) return 1; // u是v的祖先
if (isAncestor(v, u)) return 2; // v是u的祖先
return 0; // 否则，返回0
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int N, M, root; // 节点数，查询数，root为根节点
cin >> N; // 读入节点数
for (int i = 1, u, v; i <= N; i++) {
cin >> u >> v;
if (v == -1)
root = u; // 如果v为-1，则u为根节点
else
G[u].push_back(v), G[v].push_back(u); // 将u和v互相添加为邻接节点
}
dfs(root); // 从根节点开始深度优先搜索，记录时间戳
cin >> M; // 读入查询数
for (int i = 1, u, v; i <= M; i++) cin >> u >> v, printf("%d\n", solve(u, v));
return 0;
}
