（题目描述略）
纯数据结构题，不管是树分块也好，还是树套树也罢。基本思想是将每一次复制操作中新增的所有点看作一个块，这样加上初始的模板树也看作一个块，若复制了 m 次则将大树分成 m + 1 块。将大树看作是 m + 1 个节点构成的树，每个节点代表一个块，相邻节点间距离为相应块中深度最小节点的深度差。每次求两个节点间距离时，将两个节点所在块的编号求出，然后将路径分为块内路径和块间路径，分别解决求和即可。
首先对模板树深度优先搜索，完成相应的倍增求最近公共祖先的预处理。对于第 i 次将模板树中以 fr[i] 为根的子树复制到大树中 to[i] 节点下的操作，通过记录每次复制后大树的总节点数，二分求出 to[i] 节点所在块编号 to1[i]，用求区间第 k 大的方法求出 to[i] 节点在模板树中的编号 to0[i]，此处需维护一个划分树或主席树。然后，在块 to1[i] 和块 i 间建一条从 to1[i] 指向 i 的，权值为模板树中编号为 fr[to1[i]] 和 to0[i] 间深度差加一的有向边。在 m 次复制操作完成后，对 m + 1 个块构成的树深度优先搜索，完成相应的倍增求最近公共祖先的预处理。
对于大树中编号为 u 和编号为 v 的节点间距离的查询，首先二分求出 u 和 v 节点所在块编号 u1 和 v1，并求出其分别在块内距离相应块的根的距离。而后，通过倍增数组将 u1 和 v1 上移至同一深度，再一同上移，同时记录路径权值和，直至到达以下状态之一： 状态 1：u1 和 v1 块的父节点相同，且 u1 和 v1 块节点不相同。将权值和加上模板树中编号为 to0[u1] 和 to0[v1] 节点间的距离即为答案，而后者可以通过求模板树中两节点的最近公共祖先而得到。 状态 2：u1 块的父节点为 v1 块，或 v1 块的父节点为 u1 块。不失一般性的，不妨令 u1 块的父节点为 v1 块，则必有 v1 节点块无上移过程（否则为状态 1），求出大树中编号为 v 节点在模板树中的编号 v0，则将权值和加上模板树中编号为 to0[u1] 和 v0 节点间的距离即为答案。 状态 3：u1 块和 v1 块相同。此时必有 u1 和 v1 节点块无上移过程（否则若有一个节点块存在上移过程则为状态 2，若两个节点块均存在上移过程则为状态 1），求出大树中编号为 u 和 v 节点在模板树中的编号 u0 和 v0，则模板树中编号为 u0 和 v0 节点间的距离即为答案。
由于数据规模较大，加上此算法常数较大，故需加上输入输出优化此算法才能勉强通过测评。由于复制过程大树节点数可能超过 integer 整型范围，故在必要的地方数值需用 long long integer 超长整型表示。
代码如下：
#include"stdio.h" #include"string.h" #define MAX_N (100005) #define Exchange(a,b,type) \ { \ type __tmp_a=a; \ a=b,b=__tmp_a; \ } #define Read(x) \ { \ char __tmp_c=getchar();x=0; \ while(__tmp_c<'0'||__tmp_c>'9') \ __tmp_c=getchar(); \ while(__tmp_c>='0'&&__tmp_c<='9') \ x=x*10+__tmp_c-'0', \ __tmp_c=getchar(); \ } char str[25]; int dep0[MAX_N],dep1[MAX_N],fedg0[MAX_N],fedg1[MAX_N],ft[MAX_N],_index=0,m,prev0[MAX_N][20],prev1[MAX_N][20],st[MAX_N]; long long dist[MAX_N]; struct E { int next,to; }edge0[MAX_N<<1],edge1[MAX_N]; struct PARTITION_TREE { int sum[20][MAX_N],val[20][MAX_N]; void build(int f,int l,int r) { int m=(l+r+1)/2,pl=l,pr=(l+r+1)/2; for(int i=l;i<r;i++) { sum[f][i]=i>l?sum[f][i-1]:0; if(m>val[f][i]) val[f+1][pl++]=val[f][i],++sum[f][i]; else val[f+1][pr++]=val[f][i]; } if(l+1<m) build(f+1,l,m); if(m+1<r) build(f+1,m,r); } int query(int f,int l,int r,int ql,int qr,int p) { if(ql==qr) return val[f][ql]; int m=(l+r+1)/2,lt=l<ql?sum[f][ql-1]:0; if(p<=sum[f][qr]-lt) return query(f+1,l,m,l+lt,l+sum[f][qr]-1,p); else return query(f+1,m,r,m+ql-l-lt,m+qr-l-sum[f][qr],p-sum[f][qr]+lt); } }partree; struct COPY { int fr,to0,to1; long long sum,to; }maintain[MAX_N]; void dfs0(int now,int fah) { st[now]=++_index; partree.val[0][_index]=now; dep0[now]=dep0[fah]+1,prev0[now][0]=fah; for(int i=0;prev0[now][i]>-1;i++) prev0[now][i+1]=prev0[prev0[now][i]][i]; for(int i=fedg0[now];i>-1;i=edge0[i].next) if(edge0[i].to!=fah) dfs0(edge0[i].to,now); ft[now]=_index; } int biquery(int rt,long long p) { int lt=0,md; while(lt+1<rt) { md=(lt+rt)/2; if(maintain[md].sum>=p) rt=md; else lt=md; } return rt; } void dfs1(int now,int fah) { dep1[now]=dep1[fah]+1,prev1[now][0]=fah; dist[now]=dist[fah]+dep0[maintain[now].to0]-dep0[maintain[fah].fr]+1; for(int i=0;prev1[now][i]>-1;i++) prev1[now][i+1]=prev1[prev1[now][i]][i]; for(int i=fedg1[now];i>-1;i=edge1[i].next) dfs1(edge1[i].to,now); } int query0(int u,int v) { int res=dep0[u]+dep0[v]; if(dep0[u]<dep0[v]) Exchange(u,v,int); for(int i=19;i>=0&&dep0[u]>dep0[v];i--) if(1<<i<=dep0[u]-dep0[v]) u=prev0[u][i]; for(int i=19;i>=0&&u!=v;i--) if(prev0[u][i]!=prev0[v][i]) u=prev0[u][i],v=prev0[v][i]; if(u!=v) u=prev0[u][0],v=prev0[v][0]; return res-2*dep0[u]; } long long query1(long long fr,long long to) { int fr0,to0,u=biquery(m+1,fr),v=biquery(m+1,to); fr0=partree.query(0,1,_index+1,st[maintain[u].fr],ft[maintain[u].fr],(int)(fr-maintain[u-1].sum)); to0=partree.query(0,1,_index+1,st[maintain[v].fr],ft[maintain[v].fr],(int)(to-maintain[v-1].sum)); long long res=dep0[fr0]-dep0[maintain[u].fr]+dep0[to0]-dep0[maintain[v].fr]+dist[u]+dist[v]; if(dep1[u]<dep1[v]) { Exchange(fr,to,long long); Exchange(fr0,to0,int); Exchange(u,v,int); } for(int i=19;i>=0&&dep1[u]>dep1[v];i--) if(1<<i<dep1[u]-dep1[v]) u=prev1[u][i]; if(dep1[u]==dep1[v]+1&&prev1[u][0]!=v) u=prev1[u][0]; if(dep1[u]==dep1[v]) for(int i=19;i>=0&&u!=v;i--) if(prev1[u][i]!=prev1[v][i]) u=prev1[u][i],v=prev1[v][i]; res-=dist[u]+dist[v]-2; if(u!=v&&dep1[u]==dep1[v]) fr0=maintain[u].to0,to0=maintain[v].to0; else if(u!=v) fr0=maintain[u].to0,res-=dep0[to0]-dep0[maintain[v].fr]+1; else res-=dep0[fr0]-dep0[maintain[u].fr]+dep0[to0]-dep0[maintain[v].fr]+2; res+=query0(fr0,to0); return res; } void Write(long long x) { if(x==0) putchar('0'); for(str[0]=0;x>0;x/=10) str[++str[0]]=x%10+'0'; while(str[0]>0) putchar(str[str[0]--]); } int main() { freopen("tree.in","r",stdin); freopen("tree.out","w",stdout); int q;long long fr,to; Read(maintain[1].sum);Read(m);Read(q); memset(fedg0,-1,sizeof(fedg0)); for(int i=1;i<maintain[1].sum;i++) { Read(edge0[i<<1].to);Read(edge0[i<<1^1].to); edge0[i<<1].next=fedg0[edge0[i<<1^1].to]; edge0[i<<1^1].next=fedg0[edge0[i<<1].to]; fedg0[edge0[i<<1^1].to]=i<<1; fedg0[edge0[i<<1].to]=i<<1^1; } memset(prev0,-1,sizeof(prev0)); dep0[0]=-1,dfs0(1,0); partree.build(0,1,_index+1); maintain[1].fr=1,maintain[0].sum=maintain[1].to=maintain[1].to0=maintain[1].to1=0; memset(fedg1,-1,sizeof(fedg1)); for(int i=2;i<=m+1;i++) { Read(maintain[i].fr);Read(maintain[i].to); maintain[i].to1=biquery(i,maintain[i].to); maintain[i].to0=partree.query(0,1,_index+1,st[maintain[maintain[i].to1].fr],ft[maintain[maintain[i].to1].fr],maintain[i].to-maintain[maintain[i].to1-1].sum); maintain[i].sum=maintain[i-1].sum+ft[maintain[i].fr]-st[maintain[i].fr]+1; edge1[i].next=fedg1[maintain[i].to1],edge1[i].to=i; fedg1[maintain[i].to1]=i; } memset(prev1,-1,sizeof(prev1)); dep1[0]=dist[0]=-1,dfs1(1,0); while(q--) { Read(fr);Read(to); Write(query1(fr,to));putchar('\n'); } return 0; }