摘自：
本题是图论题
根据题意，判断一颗树中，某个点是否是另一个点的后裔。根据递归函数的入栈出栈时间戳特点（即子结点的入栈时间戳要晚于自己，而且子节点的出栈时间戳要早于自己）或者括号定理在O(N)内预处理一遍图，即可在O(1)时间完成每次查询。
d[x]表示深度优先搜索中x的访问时间戳
f[x]表示深度优先搜索中x的结束访问时间戳
如果d[u] < d[v] < f[v] < f[u]，那么v是u的后裔。
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 const int N = 100005; 8 9 bool color[N];10 int d[N], f[N], times;11 struct edge {12 int v;13 edge *next;14 edge(int vv, edge *p) {15 v = vv;16 next = p;17 }18 };19 20 struct graph {21 edge *link;22 }G[N];23 24 void initG(int n) {25 for (int i=1; i<=n; ++i) G[i].link = NULL;26 }27 28 void buildG(int u, int v) {29 edge *p = new edge(v, G[u].link);30 G[u].link = p;31 }32 33 void dfsVisit(int u) {34 color[u] = true;35 d[u] = times = times + 1;36 for (edge *p=G[u].link; p; p=p->next) {37 if (!color[p->v]) dfsVisit(p->v);38 }39 f[u] = times = times + 1;40 }41 42 void dfs(int n, int s) {43 for (int i=1; i<=n; ++i) color[i] = false;44 times = 0;45 for (edge *p=G[s].link; p; p=p->next) {46 if (!color[p->v]) dfsVisit(p->v);47 }48 }49 50 void del(edge *p) {51 if (!p) return ;52 del(p->next);53 delete p;54 }55 56 int main() {57 int t;58 scanf ("%d", &t);59 while (t--) {60 int q, n, u, v, s;61 scanf ("%d", &n);62 initG(n);63 for (int i=1; i<=n; ++i) {64 scanf ("%d", &u);65 if (u) buildG(u, i);66 else s = i;67 }68 buildG(s, s);69 dfs(n, s);70 scanf ("%d", &q);71 while (q--) {72 scanf ("%d%d", &u, &v);73 if (d[u] < d[v] && f[v] < f[u]) printf ("%d>%d\n", u, v);74 else if (d[v] < d[u] && f[u] < f[v]) printf ("%d<%d\n", u, v);75 else printf ("%d<>%d\n", u, v);76 }77 for (int i=1; i<=n; ++i) del(G[i].link);78 }79 return 0;80 }