这道题在LA是挂掉了，不过还好，zoj上也有这道题。
题意：好大一颗树，询问父子关系。。考虑最坏的情况，30w层，2000w个点，询问100w次，貌似连dfs一遍都会TLE。
安心啦，这肯定是一道正常人能做的题目。不过是需要几个小技巧。
1、2000w个点不一定都要保存下来，事实上，虽然题目给了256M的空间，只要开了两个这么大的数组，MLE是跑不了的，所以只保存30w个父节点。
2、如果这30w个父节点构成一条链，dfs的栈肯定爆。所以需要用栈模拟dfs。这里用的是stack<int>，当然手写栈会更快。
注意：1、时间戳的使用。
2、本题中顺序对节点标号，使得所有>=n的节点都是叶子节点，同时能够二分也是因为它是有序的。
1 #include<cstdio> 2 #include<cstring> 3 #include<stack> 4 #include<algorithm> 5 using namespace std; 6 7 const int MAXN=333333; 8 9 struct Point{ 10 int l,r; 11 }point[MAXN]; 12 13 struct T{ 14 int in,out; 15 }tim[MAXN]; 16 17 int child[MAXN],dfs_clock; 18 stack<int>stk; 19 20 void init() 21 { 22 dfs_clock=0; 23 while(!stk.empty()) 24 stk.pop(); 25 } 26 27 void dfs(int n) 28 { 29 init(); 30 stk.push(0); 31 tim[0].in=++dfs_clock; 32 child[0]=1; 33 while(!stk.empty()) 34 { 35 int x=stk.top(); 36 int r=point[x].r; 37 if(child[x]>r||child[x]>=n){ 38 tim[x].out=++dfs_clock; 39 stk.pop(); 40 }else { 41 stk.push(child[x]); 42 tim[child[x]].in=++dfs_clock; 43 child[child[x]]=point[child[x]].l; 44 child[x]++; 45 } 46 } 47 } 48 49 int find(int x,int n)//找父节点：利用顺序编码进行二分 50 { 51 int l=0,r=n-1; 52 while(l<r) 53 { 54 55 int m=l+(r-l+1)/2; 56 if(point[m].l<=x&&point[m].r>=x) 57 return m; 58 if(point[m].l>x) 59 r=m-1; 60 else 61 l=m; 62 } 63 return l; 64 } 65 66 int main() 67 { 68 int TT; 69 scanf("%d",&TT); 70 71 int n; 72 for(int cas=1;cas<=TT;cas++) 73 { 74 scanf("%d",&n); 75 int x,y=1; 76 for(int i=0;i<n;i++) 77 { 78 scanf("%d",&x); 79 point[i].l=y; 80 point[i].r=y+x-1; 81 y+=x; 82 } 83 84 dfs(n); 85 86 int m,u,v,pv; 87 scanf("%d",&m); 88 printf("Case %d:\n",cas); 89 int flog; 90 for(int i=0;i<m;i++) 91 { 92 flog=0; 93 scanf("%d%d",&u,&v); 94 95 if(u<n&&v<n){ 96 if(tim[u].in<tim[v].in&&tim[u].out>tim[v].out) 97 flog=1; 98 } 99 else if(u<n&&v>=n){//u<n漏掉了，导致RE；若u>=n，那么u就是叶子节点，不可能是父亲 100 pv=find(v,n); 101 if(tim[u].in<=tim[pv].in&&tim[u].out>=tim[pv].out) 102 flog=1; 103 } 104 105 if(flog) 106 printf("Yes\n"); 107 else 108 printf("No\n"); 109 } 110 if(cas!=TT) 111 puts(""); 112 } 113 114 return 0; 115 }