LA 3486 Cells（判祖先+栈模拟dfs）

题意：

判断u是否是v的祖先。

思路：

很简单，dfs遍历，记录每个节点第一次访问时的时间戳 in[i] 和第二次访问时的时间戳 out[i]，如果满足in[x]<in[y]<out[x]，那么x就是y的祖先。

用dfs实现是很容易的事，但这题需要用栈来模拟一下。

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstring>
 4 #include<cstdio>
 5 #include<sstream>
 6 #include<vector>
 7 #include<stack>
 8 #include<queue>
 9 #include<cmath>
10 #include<map>
11 #include<set>
12 using namespace std;
13 typedef long long ll;
14 typedef pair<int,int> pll;
15 const int INF = 0x3f3f3f3f;
16 const int maxn=20000000+5;
17 
18 int n, m;
19 int start[maxn];
20 int c[maxn];
21 int in[maxn];
22 int out[maxn];
23 
24 void dfs(int u)
25 {
26     stack<int> S;
27     int dfs_clock=0;
28     in[u]=0;
29     S.push(u);
30     while(!S.empty())
31     {
32         int x=S.top();
33         if(in[x])
34         {
35             out[x]=++dfs_clock;
36             S.pop();
37             continue;
38         }
39         in[x]=++dfs_clock;
40         for(int i=start[x];i<start[x]+c[x];i++)
41         {
42             if(i<n)  {in[i]=0;S.push(i);}
43             else  {in[i]=++dfs_clock;out[i]=++dfs_clock;}
44         }
45     }
46 }
47 
48 int main()
49 {
50     //freopen("in.txt","r",stdin);
51     int T; int kase=0;
52     scanf("%d",&T);
53     while(T--)
54     {
55         scanf("%d",&n);
56         int s=1;
57         for(int i=0;i<n;i++)
58         {
59             scanf("%d",&c[i]);
60             start[i]=s; s+=c[i];
61         }
62         dfs(0);
63         printf("Case %d:
",++kase);
64         int q;
65         scanf("%d",&q);
66         while(q--)
67         {
68             int u,v;
69             scanf("%d%d",&u,&v);
70             if(in[u]<in[v] && out[u]>in[v])  puts("Yes");
71             else puts("No");
72         }
73         if(T) puts("");
74     }
75     return 0;
76 }