小A想做一棵很大的树，但是他手上的材料有限，只好用点小技巧了。开始，小A只有一棵结点数为N的树，结
点的编号为1,2,…,N，其中结点1为根；我们称这颗树为模板树。小A决定通过这棵模板树来构建一颗大树。构建过
程如下：（1）将模板树复制为初始的大树。（2）以下(2.1)(2.2)(2.3)步循环执行M次（2.1）选择两个数字a,b，
其中1<=a<=N，1<=b<=当前大树的结点数。（2.2）将模板树中以结点a为根的子树复制一遍，挂到大树中结点b的下
方(也就是说，模板树中的结点a为根的子树复制到大树中后，将成为大树中结点b的子树)。（2.3）将新加入大树
的结点按照在模板树中编号的顺序重新编号。例如，假设在进行2.2步之前大树有L个结点，模板树中以a为根的子
树共有C个结点，那么新加入模板树的C个结点在大树中的编号将是L+1,L+2,…,L+C；大树中这C个结点编号的大小
顺序和模板树中对应的C个结点的大小顺序是一致的。下面给出一个实例。假设模板树如下图：

根据第(1)步，初始的大树与模板树是相同的。在(2.1)步，假设选择了a=4，b=3。运行(2.2)和(2.3)后，得到新的
大树如下图所示

现在他想问你，树中一些结点对的距离是多少。

　　第一行三个整数：N,M,Q，以空格隔开，N表示模板树结点数，M表示第(2)中的循环操作的次数，Q 表示询问数
量。接下来N-1行，每行两个整数 fr,to，表示模板树中的一条树边。再接下来M行，每行两个整数x,to，表示将模
板树中 x 为根的子树复制到大树中成为结点to的子树的一次操作。再接下来Q行，每行两个整数fr,to，表示询问
大树中结点 fr和 to之间的距离是多少。N,M,Q<=100000

　　输出Q行，每行一个整数，第 i行是第 i个询问的答案。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 typedef long long lol;

 struct ZYYS

 {

   lol rt,id,pre;

   lol l,r;

 }a[];

 lol pos,ch[][],sum[],n,m,root[];

 lol ans;

 struct Tree

 {

   struct Node

   {

     lol next,to;

     lol dis;

   }edge[];

   lol head[],num,dep[],size[],id[],lx[],rx[],top[],cnt,son[],fa[];

   lol d[];

   void add(lol u,lol v,lol dis)

   {

     num++;

     edge[num].next=head[u];

     head[u]=num;

     edge[num].to=v;

     edge[num].dis=dis;

   }

   void dfs1(lol x,lol pa)

   {lol i;

     dep[x]=dep[pa]+;

     size[x]=;

     fa[x]=pa;

     for (i=head[x];i;i=edge[i].next)

       {

     lol v=edge[i].to;

     if (v!=pa)

       {

         d[v]=d[x]+edge[i].dis;

         dfs1(v,x);

         size[x]+=size[v];

         if (size[v]>size[son[x]]) son[x]=v;

       }

       }

   }

   void dfs2(lol x,lol pa,lol tp)

   {lol i;

     lx[x]=++cnt;

     id[cnt]=x;

     top[x]=tp;

     if (son[x])

       {

     dfs2(son[x],x,tp);

       }

     for (i=head[x];i;i=edge[i].next)

       {

     lol v=edge[i].to;

     if (v==pa||v==son[x]) continue;

     dfs2(v,x,v);

       }

     rx[x]=cnt;

   }

   lol gettop(lol x,lol y)

   {lol z;

     while (top[x]!=top[y])

       {

     z=top[x];

     x=fa[top[x]];

       }

     if (x==y) return z;

     return son[y];

   }

   lol lca(lol x,lol y)

   {

     while (top[x]!=top[y])

       {

     if (dep[top[x]]<dep[top[y]]) swap(x,y);

     x=fa[top[x]];

       }

     if (dep[x]>dep[y]) swap(x,y);

     return x;

   }

   lol dist(lol x,lol y)

   {

     return d[x]+d[y]-*d[lca(x,y)];

   }

 }t1,t2;

 lol getid(lol k,lol r)

 {

   lol l=,as=;

   while (l<=r)

     {

       lol mid=(l+r)/;

       if (a[mid].l<=k) as=mid,l=mid+;

       else r=mid-;

     }

   return as;

 }

 void update(lol x,lol &y,lol l,lol r,lol k)

 {

   y=++pos;

   ch[y][]=ch[x][];ch[y][]=ch[x][];

   sum[y]=sum[x]+;

   if (l==r) return;

   lol mid=(l+r)/;

   if (k<=mid) update(ch[x][],ch[y][],l,mid,k);

   else update(ch[x][],ch[y][],mid+,r,k);

 }

 lol query(lol x,lol y,lol l,lol r,lol k)

 {

   if (l==r) return l;

   lol mid=(l+r)/;

   lol zyys=sum[ch[y][]]-sum[ch[x][]];

   if (zyys<k) return query(ch[x][],ch[y][],mid+,r,k-zyys);

   else return query(ch[x][],ch[y][],l,mid,k);

 }

 int main()

 {lol i,Q;

   lol x,y,u,v;

   cin>>n>>m>>Q;

   for (i=;i<=n-;i++)

     {

       scanf("%lld%lld",&u,&v);

       t1.add(u,v,);

       t1.add(v,u,);

     }

   t1.dfs1(,);

   t1.dfs2(,,);

   for (i=;i<=n;i++)

     update(root[i-],root[i],,n,t1.id[i]);

   a[].id=;a[].rt=;a[].l=;a[].r=n;

   for (i=;i<=m;i++)

     {

       scanf("%lld%lld",&x,&y);

       a[i+].id=i+;a[i+].rt=x;

       a[i+].l=a[i].r+;

       a[i+].r=a[i+].l+t1.size[x]-;

       lol z=getid(y,i);

       a[i+].pre=y=query(root[t1.lx[a[z].rt]-],root[t1.rx[a[z].rt]],,n,y-a[z].l+);

       t2.add(z,i+,t1.d[y]-t1.d[a[z].rt]+);

       t2.add(i+,z,t1.d[y]-t1.d[a[z].rt]+);

     }

   t2.dfs1(,);t2.dfs2(,,);

   for (i=;i<=Q;i++)

     {

       scanf("%lld%lld",&x,&y);

       lol p=getid(x,m+),q=getid(y,m+);

       lol w=t2.lca(p,q);

       lol u=query(root[t1.lx[a[p].rt]-],root[t1.rx[a[p].rt]],,n,x-a[p].l+);

       lol v=query(root[t1.lx[a[q].rt]-],root[t1.rx[a[q].rt]],,n,y-a[q].l+);

       if (p==q)

     {

       printf("%lld\n",t1.dist(u,v));

     }

       else

     {

       if (p==w) swap(p,q),swap(u,v);

       if (q==w)

         {

           x=t2.gettop(p,w);

           ans=t2.d[p]-t2.d[x]+t1.d[u]-t1.d[a[p].rt];

           u=a[x].pre;

           ans+=t1.dist(u,v)+;

         }

       else

         {

           ans=(t1.d[u]-t1.d[a[p].rt]+t1.d[v]-t1.d[a[q].rt]);

           ans+=t2.dist(p,q);

           x=t2.gettop(p,w);y=t2.gettop(q,w);

           u=a[x].pre;v=a[y].pre;

           ans+=(t1.d[a[w].rt]-t1.d[t1.lca(u,v)])*;

         }

       printf("%lld\n",ans);

     }

     }

 }