Description
小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个结点的大小顺序是一致的。
下面给出一个实例。假设模板树如下图：
.png)
根据第(1)步，初始的大树与模板树是相同的。
在(2.1)步，假设选择了a=4，b=3。运行(2.2)和(2.3)后，得到新的大树如下图所示.png)
现在他想问你，树中一些结点对的距离是多少。
Input
第一行三个整数：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
Output
输出Q行，每行一个整数，第 i行是第 i个询问的答案。
Sample Input
5 2 3
1 4
1 3
4 2
4 5
4 3
3 2
6 9
1 8
5 3
1 4
1 3
4 2
4 5
4 3
3 2
6 9
1 8
5 3
Sample Output
6
3
3
3
3
HINT
经过两次操作后，大树变成了下图所示的形状：.png)
结点6到9之间经过了6条边，所以距离为6；类似地，结点1到8之间经过了3条边；结点5到3之间也经过了3条边。
题解Here!
真心不想复制了，请您戳这里。
顺手贴上代码：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define MAXN 100010
using namespace std;
int n,m,q,c=1;
int id[MAXN],pos[MAXN],tree_size[MAXN];
inline long long read(){
long long date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
namespace ST{
int d=1,e=1;
int head[MAXN],deep[MAXN],f[MAXN][20];
struct Tree{
int next,to;
}a[MAXN<<1];
inline void add(int x,int y){
a[d].to=y;a[d].next=head[x];head[x]=d++;
a[d].to=x;a[d].next=head[y];head[y]=d++;
}
void buildtree(int rt){
tree_size[rt]=1;
id[rt]=e;pos[e++]=rt;
for(int i=head[rt];i;i=a[i].next){
int will=a[i].to;
if(!deep[will]){
deep[will]=deep[rt]+1;
f[will][0]=rt;
buildtree(will);
tree_size[rt]+=tree_size[will];
}
}
}
void step(){
for(int i=1;i<=19;i++)
for(int j=1;j<=n;j++)
f[j][i]=f[f[j][i-1]][i-1];
}
int LCA(int x,int y){
if(deep[x]<deep[y])swap(x,y);
for(int i=19;i>=0;i--)if(deep[f[x][i]]>=deep[y])x=f[x][i];
if(x==y)return x;
for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}
return f[x][0];
}
inline long long dis(int x,int y){return abs(deep[x]-deep[y]);}
inline long long dis_lca(int x,int y,int rt){return deep[LCA(x,y)]-deep[rt];}
}
namespace CT{
int d=1,size=1,root[MAXN];
struct Charman_Tree{
int l,r,sum;
}a[MAXN*22];
struct Right{
int root,x;
long long v;
friend bool operator <(const Right p,const Right q){return p.v<q.v;}
}right[MAXN];
void insert(int k,int l,int r,int &rt){
a[size]=a[rt];rt=size++;
a[rt].sum++;
if(l==r)return;
int mid=l+r>>1;
if(k<=mid)insert(k,l,mid,a[rt].l);
else insert(k,mid+1,r,a[rt].r);
}
int query(int i,int j,int l,int r,int k){
if(l==r)return l;
int mid=l+r>>1,t=a[a[j].l].sum-a[a[i].l].sum;
if(k<=t)return query(a[i].l,a[j].l,l,mid,k);
else return query(a[i].r,a[j].r,mid+1,r,k-t);
}
inline void buildtree(){
root[0]=0;
a[0].l=a[0].r=a[0].sum=0;
for(int i=1;i<=n;i++){
root[i]=root[i-1];
insert(pos[i],0,n,root[i]);
}
}
inline int kth(int l,int r,int k){return query(root[l],root[r],0,n,k);}
inline void insert_node(int root,int x){
right[d]=(Right){root,x,right[d-1].v+tree_size[root]};
d++;
}
inline void query_node(long long v,int &root,int &y,int &x){
Right p=*lower_bound(right+1,right+d,(Right){0,0,v});
root=p.root;x=p.x;
int rank=v+tree_size[root]-p.v;
y=kth(id[root]-1,id[root]+tree_size[root]-1,rank);
}
}
namespace BT{
int d=1,head[MAXN],deep[MAXN],val[MAXN],f[MAXN][20];
long long dis[MAXN];
struct Tree{
int next,to;
long long w;
}a[MAXN<<1];
inline void add(int u,int v,long long w){
a[d].to=v;a[d].w=w;a[d].next=head[u];head[u]=d++;
a[d].to=u;a[d].w=w;a[d].next=head[v];head[v]=d++;
}
void buildtree(int rt){
int will;
for(int i=head[rt];i;i=a[i].next){
will=a[i].to;
if(!deep[will]){
deep[will]=deep[rt]+1;
dis[will]=dis[rt]+a[i].w;
f[will][0]=rt;
buildtree(will);
}
}
}
void step(){
for(int i=1;i<=19;i++)
for(int j=1;j<=c-1;j++)
f[j][i]=f[f[j][i-1]][i-1];
}
int LCA(int x,int y,int &u,int &v){
if(x==y)return x;
if(deep[x]<deep[y]){swap(x,y);swap(u,v);}
for(int i=19;i>=0;i--)if(deep[f[x][i]]>deep[y])x=f[x][i];
if(f[x][0]==y){u=val[x];return y;}
else if(deep[x]!=deep[y])x=f[x][0];
for(int i=19;i>=0;i--)if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}
u=val[x];v=val[y];
return f[x][0];
}
inline long long dist(int u,int v,int lca){return dis[u]+dis[v]-dis[lca]*2;}
}
inline void solve(long long x,long long y){
long long dist;
int r1,x1,y1,h1;int r2,x2,y2,h2;
CT::query_node(x,r1,y1,x1);CT::query_node(y,r2,y2,x2);
h1=y1;h2=y2;
int lca=BT::LCA(x1,x2,h1,h2),r=CT::right[lca].root;
dist=ST::dis(r1,y1)+ST::dis(r2,y2)-ST::dis_lca(h1,h2,r)*2+BT::dist(x1,x2,lca);
printf("%lld
",dist);
}
void work(){
long long x,y;
while(q--){
x=read();y=read();
solve(x,y);
}
}
void init(){
int x,y,rt;
n=read();m=read();q=read();
for(int i=1;i<n;i++){
x=read();y=read();
ST::add(x,y);
}
ST::deep[1]=1;
ST::buildtree(1);
ST::step();
CT::buildtree();
CT::insert_node(1,c++);
for(int i=1;i<=m;i++){
int u=read();
long long v=read();
CT::query_node(v,rt,y,x);
CT::insert_node(u,c);
BT::val[c]=y;
int w=ST::dis(y,rt)+1;
BT::add(x,c,w);
c++;
}
BT::deep[1]=1;BT::dis[1]=0;
BT::buildtree(1);
BT::step();
}
int main(){
init();
work();
return 0;
}