这道题在LA是挂掉了，不过还好，zoj上也有这道题。
题意：好大一颗树，询问父子关系。。考虑最坏的情况，30w层，2000w个点，询问100w次，貌似连dfs一遍都会TLE。
安心啦，这肯定是一道正常人能做的题目。不过是需要几个小技巧。
1、2000w个点不一定都要保存下来，事实上，虽然题目给了256M的空间，只要开了两个这么大的数组，MLE是跑不了的，所以只保存30w个父节点。
2、如果这30w个父节点构成一条链，dfs的栈肯定爆。所以需要用栈模拟dfs。这里用的是stack<int>，当然手写栈会更快。
注意：1、时间戳的使用。
2、本题中顺序对节点标号，使得所有>=n的节点都是叶子节点，同时能够二分也是因为它是有序的。
#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std; const int MAXN=; struct Point{
int l,r;
}point[MAXN]; struct T{
int in,out;
}tim[MAXN]; int child[MAXN],dfs_clock;
stack<int>stk; void init()
{
dfs_clock=;
while(!stk.empty())
stk.pop();
} void dfs(int n)
{
init();
stk.push();
tim[].in=++dfs_clock;
child[]=;
while(!stk.empty())
{
int x=stk.top();
int r=point[x].r;
if(child[x]>r||child[x]>=n){
tim[x].out=++dfs_clock;
stk.pop();
}else {
stk.push(child[x]);
tim[child[x]].in=++dfs_clock;
child[child[x]]=point[child[x]].l;
child[x]++;
}
}
} int find(int x,int n)//找父节点：利用顺序编码进行二分
{
int l=,r=n-;
while(l<r)
{ int m=l+(r-l+)/;
if(point[m].l<=x&&point[m].r>=x)
return m;
if(point[m].l>x)
r=m-;
else
l=m;
}
return l;
} int main()
{
int TT;
scanf("%d",&TT); int n;
for(int cas=;cas<=TT;cas++)
{
scanf("%d",&n);
int x,y=;
for(int i=;i<n;i++)
{
scanf("%d",&x);
point[i].l=y;
point[i].r=y+x-;
y+=x;
} dfs(n); int m,u,v,pv;
scanf("%d",&m);
printf("Case %d:\n",cas);
int flog;
for(int i=;i<m;i++)
{
flog=;
scanf("%d%d",&u,&v); if(u<n&&v<n){
if(tim[u].in<tim[v].in&&tim[u].out>tim[v].out)
flog=;
}
else if(u<n&&v>=n){//u<n漏掉了，导致RE；若u>=n，那么u就是叶子节点，不可能是父亲
pv=find(v,n);
if(tim[u].in<=tim[pv].in&&tim[u].out>=tim[pv].out)
flog=;
} if(flog)
printf("Yes\n");
else
printf("No\n");
}
if(cas!=TT)
puts("");
} return ;
}