先离线记录所有询问，然后用dfs在线记录当前节点的所有父亲结点，父亲结点分为两类，一个从左边过来，一个从右边过来，分别开一个数组。
数据需要离散化，刚开始用lower_bound写，一直wa。。，用二分就过了。
之后总结了下lower_bound和upper_bound的规律。
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
int a[7]={5,9,13,19,25,39,100};
int main()
{
int i,j,k,n;
while(scanf("%d",&n))
{
printf("%d\n",lower_bound(a,a+7,n)-a);//第一个大于等于他的数的下标，当不存在大于等于他的数时，返回数组最后一个数下标加一
printf("%d\n",upper_bound(a,a+7,n)-a);//第一个大于他的数的下标，当不存在大于他的数时，返回数组最后一个数下标加一
}
}
下面是代码
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<vector>
#define LL long long
using namespace std;
const int maxn=100005;
int cl[100005],cr[100005],p[100005],quar,len;
int w[maxn],numl=0,numr=0,flag;
vector<int>son[100005];
vector< pair<int,int> >q[100005];
struct Q
{
int x,y;
}qq[100005];
int lowbit(int cur)
{
return cur&(-cur);
}
void update(int cur,int dir,int s)
{
if(dir==-1)
while(cur<maxn)
{
cl[cur]+=s;
cur+=lowbit(cur);
}
else
while(cur<maxn)
{
cr[cur]+=s;
cur+=lowbit(cur);
}
}
int getnum(int cur,int dir)
{
int ans=0;
if(dir==-1)
{
while(cur>0)
{
ans+=cl[cur];
cur-=lowbit(cur);
}
}
else
{
while(cur>0)
{
ans+=cr[cur];
cur-=lowbit(cur);
}
}
return ans;
}
int findcou(int cur)
{
int st=0,ed=len-1,mid;
if(p[ed]<cur)return len-1;
if(p[st]>cur)return -1;
while(st<ed)
{
mid=(st+ed)/2;
if(p[mid]==cur){flag=1;return mid;}
if(p[mid]>cur)ed=mid;
else st=mid+1;
}
if(p[st]==cur)
{
flag=1;
return st;
}
return st-1;
}
void dfs(int s)
{
int i,j,k,l,r,x,y,cou,h;
for(i=0;i<q[s].size();i++)
{
k=q[s][i].first;
// printf("s=%d,k=%d,\n",s,k);
flag=0;
k=findcou(k)+1;
//printf("s=%d,k=%d,\n",s,k);
y=numl+numr;
l=getnum(k,-1);
r=getnum(k,1);
//printf("numl=%d,numr=%d,l=%d,r=%d\n",numl,numr,l,r);
y+=2*(l+r);x=r;
if(flag)
{
if(l>0)
{
l-=getnum(k-1,-1);
if(l>0)x=y=-1;
}
if(r>0)
{
r-=getnum(k-1,1);
if(r>0)x=y=-1;
}
}
cou=q[s][i].second;
//puts("ok??");
qq[cou].x=x;qq[cou].y=y;
}
//puts("ok??");
if(son[s].size()==0)return ;
int tmp=findcou(w[s])+1;
//printf("s=%d,tmp=%d\n",s,tmp);
update(tmp,-1,1);numl++;dfs(son[s][0]);
//printf("numl=%d,numr=%d,",numl,numr);
update(tmp,-1,-1);numl--; update(tmp,1,1);numr++;dfs(son[s][1]);
update(tmp,1,-1);numr--;
}
int main()
{
int j,m,n,v,x;
int t,i,tmp,u,a,b;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&w[i]);
p[i-1]=w[i];
cl[i]=cr[i]=0;
son[i].clear();
q[i].clear();
}
sort(p,p+n);
len=unique(p,p+n)-p;
scanf("%d",&m);
for(i=0;i<m;i++)
{
scanf("%d%d%d",&u,&a,&b);
son[u].push_back(a);
son[u].push_back(b);
// printf("%d----%d\n",u,son[u].size());
}
scanf("%d",&quar);
for(i=0;i<quar;i++)
{
scanf("%d%d",&v,&x);
q[v].push_back(make_pair(x,i));
//printf("%d-----%d\n",i,q[v].size());
}
//for(i=0;i<=len;i++)
//printf("%d,",p[i]);
numr=numl=0;
dfs(1);
for(i=0;i<quar;i++)
if(qq[i].x==qq[i].y&&qq[i].x==-1)
puts("0");
else
printf("%d %d\n",qq[i].x,qq[i].y);
}
return 0;
}