记录编号	389504	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HNOI 2016] 树	最终得分	100
用户昵称	Cydiater	是否通过	通过
代码语言	C++	运行时间	9.995 s
提交时间	2017-03-31 18:18:45	内存使用	104.08 MiB

//BZOJ 4539
//by Cydiater
//2017.3.31
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define up(i,j,n)	for(ll i=j;i<=n;i++)
#define down(i,j,n)	for(ll i=j;i>=n;i--)
#define cmax(a,b)	a=max(a,b)
#define cmin(a,b)	a=min(a,b)
#define Auto(i,node)	for(ll i=LINK[node];i;i=e[i].next)
#define FILE		"tree_tenderRun"

const ll MAXN=1e5+5;
const ll oo=1LL<<40;

ll N,M,Q,rtlist[MAXN],top=0,tol=0,rtf[MAXN];
map<ll,ll>T;

namespace CMT{
	struct tree{
		ll son[2],siz;
	}t[MAXN<<5];
	ll cnt=0,root[MAXN];
	int NewNode(ll s0,ll s1,ll siz){
		t[++cnt].son[0]=s0;t[cnt].son[1]=s1;
		t[cnt].siz=siz;
		return cnt;
	}
	void Build(ll leftt,ll rightt,ll &k,ll last,ll pos){
		k=NewNode(t[last].son[0],t[last].son[1],t[last].siz+1);
		int mid=(leftt+rightt)>>1;
		if(leftt==rightt)	return;
		if(pos<=mid)	Build(leftt,mid,t[k].son[0],t[last].son[0],pos);
		if(pos>=mid+1)	Build(mid+1,rightt,t[k].son[1],t[last].son[1],pos);
	}
	ll Query(ll leftt,ll rightt,ll kl,ll kr,ll rnk){
		ll lsiz=t[t[kr].son[0]].siz-t[t[kl].son[0]].siz,mid=(leftt+rightt)>>1;
		if(leftt==rightt)return leftt;
		if(rnk>lsiz)	return Query(mid+1,rightt,t[kl].son[1],t[kr].son[1],rnk-lsiz);
		else		return Query(leftt,mid,t[kl].son[0],t[kr].son[0],rnk);
	}
}using namespace CMT;

struct Graph{
	struct edge{
		ll y,next,v;
	}e[MAXN<<1];
	int LINK[MAXN],len,fa[MAXN][18],dep[MAXN],siz[MAXN],dfn[MAXN],Pos[MAXN],dfsclock,T;
	ll dis[MAXN];
	inline void insert(ll x,ll y,ll v){
		e[++len].next=LINK[x];LINK[x]=len;
		e[len].y=y;e[len].v=v;
	}
	inline void Insert(ll x,ll y,ll v){
		insert(x,y,v);
		insert(y,x,v);
	}
	void DFS(ll node,ll deep,ll father){
		fa[node][0]=father;dep[node]=deep;
		siz[node]=1;Pos[node]=++dfsclock;
		dfn[dfsclock]=node;
		Auto(i,node)if(e[i].y!=father){
			dis[e[i].y]=dis[node]+e[i].v;
			DFS(e[i].y,deep+1,node);
			siz[node]+=siz[e[i].y];
		}
	}
	void GetAnc(){
		up(i,1,17)up(node,1,T)if(fa[node][i-1])
			fa[node][i]=fa[fa[node][i-1]][i-1];
	}
	ll LCA(ll x,ll y){
		if(x==y)return x;
		if(dep[x]<dep[y])swap(x,y);
		down(i,17,0)if(dep[x]-(1<<i)>=dep[y])
			x=fa[x][i];
		if(x==y)return x;
		down(i,17,0)if(fa[x][i]&&fa[x][i]!=fa[y][i]){
			x=fa[x][i];
			y=fa[y][i];
		}
		return fa[x][0];
	}
	ll dist(ll x,ll y){
		ll lca=LCA(x,y);
		return dis[x]+dis[y]-(dis[lca]<<1);
	}
	ll anc(ll x,ll deep){
		down(i,17,0)if(dep[x]-(1<<i)>=deep)
			x=fa[x][i];
		return x;
	}
}G1,G2;

namespace solution{
	ll getroot(ll k){
		ll p=lower_bound(rtlist+1,rtlist+top+1,k)-rtlist;
		if(rtlist[p]!=k)p--;
		return p;
	}
	void Prepare(){
		scanf("%lld%lld%lld",&N,&M,&Q);
		up(i,2,N){
			ll x,y;
			scanf("%lld%lld",&x,&y);
			G1.Insert(x,y,1);
		}
		G1.DFS(1,0,0);G1.T=N;G1.GetAnc();
		up(i,1,N)Build(1,N,root[i],root[i-1],G1.dfn[i]);
		tol=N;
		rtlist[++top]=1;
		T[1]=1;
		up(i,1,M){
			ll x,y,rt;
			scanf("%lld%lld",&x,&y);
			rt=getroot(y);
			rtlist[++top]=++tol;
			T[tol]=x;
			tol+=G1.siz[x]-1;
			ll tmp=T[rtlist[rt]];
			y=Query(1,N,root[G1.Pos[tmp]-1],root[G1.Pos[tmp]+G1.siz[tmp]-1],y-rtlist[rt]+1);
			rtf[top]=y;
			G2.Insert(top,rt,G1.dep[y]-G1.dep[tmp]+1);
		}
		G2.T=top;
		G2.DFS(1,0,0);
		G2.GetAnc();
	}
	void Solve(){
		while(Q--){
			ll x,y,rx,ry,ans=0,nx,ny,nrx,nry,tx,ty;
			scanf("%lld%lld",&x,&y);
			tx=getroot(x);ty=getroot(y);
			rx=rtlist[tx];ry=rtlist[ty];
			nrx=T[rx];nry=T[ry];
			nx=Query(1,N,root[G1.Pos[nrx]-1],root[G1.Pos[nrx]+G1.siz[nrx]-1],x-rx+1);
			ny=Query(1,N,root[G1.Pos[nry]-1],root[G1.Pos[nry]+G1.siz[nry]-1],y-ry+1);
			ans=G1.dist(nx,nrx)+G1.dist(ny,nry)+G2.dist(tx,ty);
			ll lca=G2.LCA(tx,ty),ancx,ancy,RT;
			if(lca==tx&&lca==ty){
				lca=G1.LCA(nx,ny);
				RT=nrx;
			}else if(lca==tx){
				ancy=G2.anc(ty,G2.dep[lca]+1);
				lca=G1.LCA(nx,rtf[ancy]);
				RT=nrx;
			}else if(lca==ty){
				ancx=G2.anc(tx,G2.dep[lca]+1);
				lca=G1.LCA(ny,rtf[ancx]);
				RT=nry;
			}else{
				ancx=G2.anc(tx,G2.dep[lca]+1);
				ancy=G2.anc(ty,G2.dep[lca]+1);
				lca=G1.LCA(rtf[ancx],rtf[ancy]);
				RT=T[rtlist[G2.fa[ancx][0]]];
			}
			ans-=((G1.dep[lca]-G1.dep[RT])<<1);
			printf("%lld\n",ans);	
		}
	}
}

int main(){
	//freopen("input.in","r",stdin);
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	using namespace solution;
	Prepare();
	Solve();
	return 0;
}