BZOJ 4539: [Hnoi 2016] tree

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=100000+5;
#define rep(i,l,r) for(int i=l;i<=r;i++)
typedef long long ll;
ll read(){
	char ch=getchar();ll x=0,f=1;
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
struct Edge{int to,next;}e[N<<1],g[N<<1];
int head[N],cnt,last[N],tot;
void ins1(int u,int v){e[++cnt]=(Edge){v,head[u]};head[u]=cnt;}
void insert1(int u,int v){ins1(u,v);ins1(v,u);}
void ins2(int u,int v){g[++tot]=(Edge){v,last[u]};last[u]=tot;}
void insert2(int u,int v){ins2(u,v);ins2(v,u);}
int fa1[N],dep1[N],top1[N],son1[N],siz1[N],st[N],ed[N],dfn[N],sz;
void dfs1(int u){
	dfn[st[u]=++sz]=u;siz1[u]=1;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;if(v==fa1[u])continue;
		fa1[v]=u;dep1[v]=dep1[u]+1;dfs1(v);
		siz1[u]+=siz1[v];if(siz1[v]>siz1[son1[u]])son1[u]=v;
	}
	ed[u]=sz;
}
void dfs1(int u,int tp){
	top1[u]=tp;
	if(son1[u])dfs1(son1[u],tp);
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(v!=fa1[u]&&v!=son1[u])dfs1(v,v);
	}
}
struct Node{
	int lc,rc,w;
}tr[N*20];
int node,root[N];
void build(int &o,int l,int r){
	o=++node;
	if(l==r)return;
	int mid=l+r>>1;
	build(tr[o].lc,l,mid);build(tr[o].rc,mid+1,r);
}
void insert(int &o,int l,int r,int p){
	tr[++node]=tr[o];o=node;
	tr[o].w++;
	if(l==r)return;
	int mid=l+r>>1;
	if(p<=mid)insert(tr[o].lc,l,mid,p);
	else insert(tr[o].rc,mid+1,r,p);
}
int query(int x,int y,int l,int r,int k){
	if(l==r)return l;
	int mid=l+r>>1;
	int sum=tr[tr[y].lc].w-tr[tr[x].lc].w;
	if(k<=sum)
	return query(tr[x].lc,tr[y].lc,l,mid,k);
	else return query(tr[x].rc,tr[y].rc,mid+1,r,k-sum);
}
int rank(int x,int y,int l,int r,int k){
	if(l==r)return tr[y].w-tr[x].w;
	int mid=l+r>>1;
	if(k<=mid)return rank(tr[x].lc,tr[y].lc,l,mid,k);
	else return rank(tr[x].rc,tr[y].rc,mid+1,r,k)+tr[tr[y].lc].w-tr[tr[x].lc].w;
}
int query(int u,int k){
	return query(root[st[u]-1],root[ed[u]],1,sz,k);
}
int rank(int u,int k){
	return rank(root[st[u]-1],root[ed[u]],1,sz,k);
}
int fa2[N],dep2[N],siz2[N],son2[N],top2[N],cost[N];
ll depth[N];
void dfs2(int u){
	siz2[u]=1;
	for(int i=last[u];i;i=g[i].next){
		int v=g[i].to;if(v==fa2[u])continue;
		dep2[v]=dep2[u]+1;fa2[v]=u;depth[v]=depth[u]+cost[v];dfs2(v);
		siz2[u]+=siz2[v];if(siz2[v]>siz2[son2[u]])son2[u]=v;
	}
}
void dfs2(int u,int tp){
	top2[u]=tp;
	if(son2[u])dfs2(son2[u],tp);
	for(int i=last[u];i;i=g[i].next){
		int v=g[i].to;
		if(v!=son2[u]&&v!=fa2[u])dfs2(v,v);
	}
}
ll size[N];
int n,m,now;
int belong(ll id){
	int l=1,r=now;
	while(l<=r){
		int mid=l+r>>1;
		if(size[mid]<id)l=mid+1;
		else r=mid-1;
	}
	return l-1;
}
int lca1(int u,int v){
	while(top1[u]!=top1[v]){
		if(dep1[top1[u]]<dep1[top1[v]])swap(u,v);
		u=fa1[top1[u]];
	}
	return dep1[u]<dep1[v]?u:v;
}
ll li[N];
int rt[N];
ll lca2(ll u,ll v){
	int x=belong(u),y=belong(v);
	while(top2[x]!=top2[y]){
		if(dep2[top2[x]]<dep2[top2[y]])swap(x,y),swap(u,v);
		x=top2[x];u=li[x];x=fa2[x];
	}
	if(x!=y){
		if(dep2[x]>dep2[y])swap(x,y),swap(u,v);
		y=x;v=li[son2[y]];
	}
	return size[x]+rank(rt[x],lca1(query(rt[x],u-size[x]),query(rt[y],v-size[y])));
}
ll dep(ll u){
	int x=belong(u);
	return depth[x]+dep1[query(rt[x],u-size[x])]-dep1[rt[x]];
}
ll dist(ll u,ll v){
	return dep(u)+dep(v)-2*dep(lca2(u,v));
}
int main(){
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	int q;n=read();m=read();q=read();
	rep(i,2,n){int u,v;u=read();v=read();insert1(u,v);}
	dfs1(1);dfs1(1,1);
	build(root[0],1,sz);
	rep(i,1,sz){
		root[i]=root[i-1];
		insert(root[i],1,sz,dfn[i]);
	}
	rt[1]=1;m++;now=1;
	rep(i,2,m){
		rt[i]=read();li[i]=read();size[i]=size[i-1]+siz1[rt[i-1]];
		int x=belong(li[i]);
		insert2(i,x);
		cost[i]=dep1[query(rt[x],li[i]-size[x])]-dep1[rt[x]]+1;
		now++;
	}
	dfs2(1);dfs2(1,1);
	while(q--){
		ll u,v;u=read();v=read();
		printf("%lld
",dist(u,v));
	}
	return 0;
}