能过样例但爆零了。有人帮忙看下吗。
话说这毒瘤题以前不是黑题mia
#include<bits/stdc++.h>
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 100005
using namespace std;
int h[N],tot;
struct edge{
int to,nxt;
}e[N<<1];
void add(int x,int y){
e[++tot].nxt=h[x];h[x]=tot;e[tot].to=y;
}
int n,m,q,idx;
struct node{
int l,r,sum;
node(){l=r=sum=0;}
}a[N<<5];
void updata(int x){
a[x].sum=a[a[x].l].sum+a[a[x].r].sum;
}
int insert(int y,int l,int r,int pos){
int x=++idx;a[x]=a[y];
if(l==r){a[x].sum++;return x;}
int mid=(l+r)>>1;
if(mid>=pos)a[x].l=insert(a[y].l,l,mid,pos);
else a[x].r=insert(a[y].r,mid+1,r,pos);
updata(x);return x;
}
int ask(int x,int y,int l,int r,int k){
if(l==r)return l;
int mid=(l+r)>>1,sum=a[a[x].l].sum-a[a[y].l].sum;
if(sum>=k)return ask(a[x].l,a[y].l,l,mid,k);
return ask(a[x].r,a[y].r,mid+1,r,k-sum);
}
int t,cnt=0,d[N],f[N][20],dfn[N],sz[N],rt[N],mat[N];
void dfs(int x,int fa){
f[x][0]=fa;d[x]=d[fa]+1;dfn[x]=++cnt;sz[x]=1;mat[cnt]=x;
rep(i,1,t)f[x][i]=f[f[x][i-1]][i-1];
for(int i=h[x];i;i=e[i].nxt)if(e[i].to!=fa){
dfs(e[i].to,x);sz[x]+=sz[e[i].to];
}
}
struct seg{
int l,r;
}u[N];
int g[N][20],dis[N][20],c[N],tr[N],ud[N];
int get(int x){
int l=1,r=m+1;
while(l<=r){
int mid=(l+r)>>1;
if(u[mid].l<=x&&u[mid].r>=x)return mid;
if(u[mid].l>x)r=mid-1;
else l=mid+1;
}
return -1;
}
int calc(int x,int op){
//cout<<x<<" "<<op<<endl;
if(op==1)return d[x];
int y=c[op];
return d[ask(rt[dfn[y]+sz[y]-1],rt[dfn[y]-1],1,n,x-u[op].l+1)]-d[y];
}
int solve(int x,int y){
int uu=get(x),vv=get(y);
int sum=0;
//cout<<x<<" "<<y<<" "<<uu<<" "<<vv<<endl;
if(uu!=vv){
if(ud[uu]<ud[vv])swap(uu,vv),swap(x,y);
sum+=calc(x,uu);
//cout<<" tt "<<sum<<endl;
pre(i,t,0)if(ud[g[uu][i]]>ud[vv]){
sum+=dis[uu][i];uu=g[uu][i];
}
if(g[uu][0]==vv){
x=tr[uu];sum++;uu=g[uu][0];
}
else{
//cout<<"ss "<<sum<<endl;
if(ud[g[uu][0]]>ud[vv])uu=g[uu][0],sum+=dis[uu][0];
sum+=calc(y,vv);
//cout<<"uu "<<sum<<endl;
//printf("%d %d %d %d %d\n",uu,vv,g[uu][0],g[vv][0],sum);
pre(i,t,0)if(g[uu][i]!=g[vv][i]){
sum+=dis[uu][i]+dis[vv][i];
uu=g[uu][i];vv=g[vv][i];
}
//cout<<"vv "<<sum<<endl;
sum+=2;x=tr[uu];y=tr[vv];
uu=g[uu][0];vv=g[vv][0];
}
}
if(uu^1)x=ask(rt[dfn[c[uu]]+sz[c[uu]]-1],rt[dfn[c[uu]]-1],1,n,x-u[uu].l+1);
if(vv^1)y=ask(rt[dfn[c[vv]]+sz[c[vv]]-1],rt[dfn[c[vv]]-1],1,n,y-u[vv].l+1);
if(d[x]<d[y])swap(x,y),swap(uu,vv);
//cout<<x<<" "<<y<<" "<<sum<<endl;
pre(i,t,0)if(d[f[x][i]]>=d[y])sum+=(1<<i),x=f[x][i];
if(x==y)return sum;
pre(i,t,0)if(f[x][i]!=f[y][i])sum+=(1<<(i+1)),x=f[x][i],y=f[y][i];
return sum+2;
}
signed main(){
scanf("%lld%lld%lld",&n,&m,&q);t=log2(n);
rep(i,1,n-1){
int x,y;scanf("%lld%lld",&x,&y);
add(x,y);add(y,x);
}
dfs(1,0);rt[0]=++idx;
rep(i,1,n)rt[i]=insert(rt[i-1],1,n,mat[i]);
u[1].l=1;u[1].r=n;ud[1]=1;
rep(i,2,m+1){
int x;
scanf("%lld%lld",&c[i],&x);
int l=1,r=i-1,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(u[mid].l<=x&&u[mid].r>=x){ans=mid;break;}
if(u[mid].l>x)r=mid-1;
else l=mid+1;
}
int ds=calc(x,ans);
u[i].l=u[i-1].r+1;u[i].r=u[i].l+sz[c[i]]-1;
g[i][0]=ans;dis[i][0]=ds+1;tr[i]=x;ud[i]=ud[ans]+1;
rep(j,1,t)g[i][j]=g[g[i][j-1]][j-1],dis[i][j]=dis[i][j-1]+dis[g[i][j-1]][j-1];
}
//rep(i,1,m+1)printf("%d %d %d %d %d %d %d\n",u[i].l,u[i].r,c[i],ud[i],tr[i],g[i][0],dis[i][0]);
/*rep(i,1,n){
rep(j,0,t)printf("%d ",f[i][j]);
putchar('\n');
}*/
rep(i,1,q){
int x,y;scanf("%lld%lld",&x,&y);
printf("%lld\n",solve(x,y));
}
return 0;
}