大致题意： 给定一棵模板树，要求建立一棵大树，初始与模板树一样。每次操作将模板树中以\(x\)为根的子树复制为大树中\(y\)的子节点，将其重新编号并保持相对大小顺序不变。每次询问求两点间的距离。
建树
首先我们考虑如何建出这棵大树，由于最多有\(10^{10}\)个点，显然不可能暴力去建。
其实不难想到，可以把每棵复制到大树中的子树压缩为一个点，然后只需记录下\(Rt_i,G_i\)两个信息分别表示它的根节点为\(Rt_i\)以及它接在大树中对应到模板树编号为\(G_i\)的点之下。
至于如何求出\(G_i\)，我们只要预处理出模板树中每个点的子树大小，那么就能求出每棵复制树对应的节点编号区间，然后只要用\(upper\_bound-1\)就能求出接在哪棵复制树下。
求出复制树编号后，我们还需要求出该子树中编号排名为\(k\)的点的编号，这可以用线段树合并维护子树信息。
询问
询问其实也很简单，就是细节比较多，大致分三类讨论：
- 两点在同一棵复制树中：直接询问两点距离即可。
- 两点所在的复制树压成的点在大树上为祖先关系：从儿子倍增向上跳，最后加上儿子接入的点和祖先询问的点之间的距离。
- 两点所在的复制树压成的点在大树上不存在祖先关系：向上跳到\(LCA\)，最后加上两者接入点之间的距离。
具体实现详见代码。
代码
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 100000
#define LN 20
#define LL long long
using namespace std;
int n,m;
class OriginalTree//原树
{
private:
int ee,lnk[N+5],sz[N+5],d[N+5],f[N+5][LN+5];struct edge {int to,nxt;}e[N<<1];
class SegmentTree//线段树合并
{
private:
#define LT l,mid,O[rt].S[0]
#define RT mid+1,r,O[rt].S[1]
int Nt;struct node {int V,S[2];}O[N*LN<<1];
public:
I void Ins(CI x,CI l,CI r,int& rt)
{
if(!rt&&(rt=++Nt),++O[rt].V,l==r) return;
int mid=l+r>>1;x<=mid?Ins(x,LT):Ins(x,RT);
}
I void Merge(int& x,CI y)
{
if(!x||!y) return (void)(x|=y);O[++Nt]=O[x],O[x=Nt].V+=O[y].V,
Merge(O[x].S[0],O[y].S[0]),Merge(O[x].S[1],O[y].S[1]);
}
I int Qry(CI k,CI l,CI r,CI rt)
{
if(l==r) return l;int mid=l+r>>1;
return O[O[rt].S[0]].V>=k?Qry(k,LT):Qry(k-O[O[rt].S[0]].V,RT);
}
}S;int Rt[N+5];
I int LCA(RI x,RI y)//倍增LCA
{
RI i;d[x]<d[y]&&(x^=y^=x^=y);
for(i=0;d[x]^d[y];++i) (d[x]^d[y])>>i&1&&(x=f[x][i]);if(x==y) return x;
for(i=LN;~i;--i) f[x][i]^f[y][i]&&(x=f[x][i],y=f[y][i]);return f[x][0];
}
public:
I int operator [] (CI x) {return sz[x];}I int operator () (CI x) {return d[x];}
I void Add(CI x,CI y) {e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y;}
I void dfs(CI x=1)//预处理
{
RI i;for(i=1;i<=LN;++i) f[x][i]=f[f[x][i-1]][i-1];
for(S.Ins(x,1,n,Rt[x]),sz[x]=1,i=lnk[x];i;i=e[i].nxt) e[i].to^f[x][0]&&
(d[e[i].to]=d[f[e[i].to][0]=x]+1,dfs(e[i].to),S.Merge(Rt[x],Rt[e[i].to]),sz[x]+=sz[e[i].to]);
}
I int Dis(CI x,CI y) {return d[x]+d[y]-(d[LCA(x,y)]<<1);}//询问距离
I int Qry(CI x,CI k) {return S.Qry(k,1,n,Rt[x]);}//询问子树内相对顺序第k大的点的编号
}T;
class CompressionTree//压缩后的大树
{
private:
#define GetPos(x,i,p) (i=upper_bound(L+1,L+Vt+1,x)-L-1,p=T.Qry(Rt[i],(x)-L[i]+1))//求出复制树编号以及接入的节点编号
int ee,lnk[N+5],d[N+5],f[N+5][LN+5];struct edge {int to,nxt,val;}e[N+5];
int Vt,Rt[N+5],G[N+5];LL tot,L[N+5],R[N+5],D[N+5];
I int LCA(RI x,RI y)//倍增LCA（可直接从上面copy）
{
RI i;d[x]<d[y]&&(x^=y^=x^=y);
for(i=0;d[x]^d[y];++i) (d[x]^d[y])>>i&1&&(x=f[x][i]);if(x==y) return x;
for(i=LN;~i;--i) f[x][i]^f[y][i]&&(x=f[x][i],y=f[y][i]);return f[x][0];
}
I int Jump(RI x,CI t)//从x跳到深度t的祖先
{
for(RI i=0;d[x]^t;++i) (d[x]^t)>>i&1&&(x=f[x][i]);return x;
}
public:
I void Init() {Rt[Vt=1]=L[1]=1,tot=R[1]=n;}
I void Add(CI x,CI y,CI v) {e[++ee].nxt=lnk[x],e[lnk[x]=ee].to=y,e[ee].val=v;}
I void Ins(CI x,Con LL& y)//复制一棵树
{
Rt[++Vt]=x,L[Vt]=tot+1,R[Vt]=(tot+=T[x]);RI f;//L,R记录区间
GetPos(y,f,G[Vt]),Add(f,Vt,T(G[Vt])-T(Rt[f])+1);//注意边权
}
I void dfs(CI x=1)//初始化
{
RI i;for(i=1;i<=LN;++i) f[x][i]=f[f[x][i-1]][i-1];
for(i=lnk[x];i;i=e[i].nxt) d[e[i].to]=d[f[e[i].to][0]=x]+1,D[e[i].to]=D[x]+e[i].val,dfs(e[i].to);
}
I LL GetD(Con LL& x,Con LL& y)//询问距离
{
RI a,b,u,v;GetPos(x,a,u),GetPos(y,b,v);if(a==b) return T.Dis(u,v);RI c=LCA(a,b);//在同一棵树中直接询问
RI t;if(a==c&&(a^=b^=a^=b,u^=v^=u^=v),b==c)//为祖先关系
return t=Jump(a,d[b]+1),T(u)-T(Rt[a])+D[a]-D[t]+1+T.Dis(G[t],v);//儿子向上跳，并加上儿子接入点和祖先询问点的距离
RI A=Jump(a,d[c]+1),B=Jump(b,d[c]+1);//一起向上跳
return (T(u)-T(Rt[a])+D[a]-D[A]+1)+(T(v)-T(Rt[b])+D[b]-D[B]+1)+T.Dis(G[A],G[B]);//加上接入点间的距离
}
}S;
int main()
{
RI Qt,i,x,y;LL u,v;scanf("%d%d%d",&n,&m,&Qt);
for(i=1;i^n;++i) scanf("%d%d",&x,&y),T.Add(x,y),T.Add(y,x);T.dfs();//模板树
for(S.Init(),i=1;i<=m;++i) scanf("%d%lld",&x,&u),S.Ins(x,u);S.dfs();//大树
W(Qt--) scanf("%lld%lld",&u,&v),printf("%lld\n",S.GetD(u,v));return 0;//询问
}