传送门

题解:

一开始看错题了以为可以拷贝新加的点的，仔细一看是一道倍增裸题。
首先建一颗虚树，只存拷贝的根节点。
注意到询问两点最后肯定是到某个虚树的节点内部求$lca$。那么直接在虚树上倍增到同一个节点再在原树上倍增到$lca$即可。 时间复杂度$O(n \log n)$。
注意还要求的是一个子树中第$k$大的节点是哪一个，这个直接用$dfs$转为区间第 k k <script type="math/tex" id="MathJax-Element-108">k</script>大就行了。

#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
inline LL rd() {
    char ch=getchar(); LL i=0,f=1;
    while(!isdigit(ch)) {
   if(ch=='-')f=-1; ch=getchar();}
    while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=getchar();}
    return i*f;
}
inline void W(LL x) {
    static int buf[50];
    if(!x) {
   putchar('0'); return;}
    if(x<0) {
   putchar('-');x=-x;}
    while(x) {buf[++buf[0]]=x%10; x/=10;}
    while(buf[0]) {
   putchar(buf[buf[0]--]+'0');}
}
const int N=1e5+50;
int n,m,q;
int rt[N],lc[N*30],rc[N*30],sze[N*30],tot;
int dfn[N],last[N],dep[N],fa[N][20],ind;
vector <int> edge[N];
LL totid,cnt,vdis[N],vdep[N],vfa[N][20],vrt[N],vbg[N],vofa[N],bg[N],rt2[N],rt3[N];
set < pair<LL,int> > S;
inline int copy(int x) {++tot; lc[tot]=lc[x]; rc[tot]=rc[x]; sze[tot]=sze[x]; return tot;}
inline void inc(int x,int &y,int l,int r,int p) {
    y=copy(x); ++sze[y]; if(l==r) return;
    int mid=(l+r)>>1;
    (p<=mid)?inc(lc[x],lc[y],l,mid,p):inc(rc[x],rc[y],mid+1,r,p);
}
inline void dfs(int x,int f) {
    dfn[x]=++ind; dep[x]=dep[f]+1; fa[x][0]=f;
    inc(rt[ind-1],rt[ind],1,n,x);
    for(int i=1;i<=18;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
    for(int e=edge[x].size()-1;e>=0;e--) {
        int v=edge[x][e]; if(v==f) continue;
        dfs(v,x);
    }
    last[x]=ind;
}
const int INF=0x3f3f3f3f;
inline int getid(LL to) {
   return (--S.upper_bound(make_pair(to,INF)))->second;}
inline int getlca(int x,int y) {
    if(dep[x]<dep[y]) swap(x,y);
    int d=dep[x]-dep[y];
    for(int i=0;i<=18;i++) if(d&(1<<i)) x=fa[x][i];
    if(x==y) return x;
    for(int i=18;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
inline int calc_dis(int x,int y) {
   return dep[x]+dep[y]-2*dep[getlca(x,y)];}
inline int kth(int x,int y,int l,int r,int k) {
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(sze[lc[y]]-sze[lc[x]]>=k) return kth(lc[x],lc[y],l,mid,k);
    else return kth(rc[x],rc[y],mid+1,r,k-sze[lc[y]]+sze[lc[x]]);
}
inline int rk(int x,int y,int l,int r,int v) {
    if(l==r) return sze[y]-sze[x];
    int mid=(l+r)>>1;
    if(v<=mid) return rk(lc[x],lc[y],l,mid,v);
    else return sze[lc[y]]-sze[lc[x]]+rk(rc[x],rc[y],mid+1,r,v);
}
inline int kth(int x,int k) {
   return kth(rt[dfn[x]-1],rt[last[x]],1,n,k);}
inline int rk(int x,int k) {
   return rk(rt[dfn[x]-1],rt[last[x]],1,n,k);}
int main() {
    n=rd(), m=rd(), q=rd();
    for(int i=1;i<n;i++) {
        int x=rd(), y=rd();
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    dfs(1,0);
    totid=n;  rt3[1]=1; 
    S.insert(make_pair(1,cnt=1)); 
    for(int i=1;i<=m;i++) {
        int x=rd(); LL to=rd();
        S.insert(make_pair(totid+1,++cnt));
        bg[cnt]=totid+1;
        totid+=last[x]-dfn[x]+1;
        LL r=getid(to);
        vfa[cnt][0]=r; vofa[cnt]=to; 
        vdep[cnt]=vdep[r]+1;
        rt2[cnt]=x; rt3[cnt]=rk(x,x)+bg[cnt]-1;
        vdis[cnt]=vdis[r]+(to>n?calc_dis(kth(rt2[r],to-bg[r]+1),rt2[r]):dep[to]-1)+1;
        for(int i=1;i<=18;i++) vfa[cnt][i]=vfa[vfa[cnt][i-1]][i-1];
    }
    for(int i=1;i<=q;i++) {
        LL x=rd(), y=rd(), ans=0;
        int idx=getid(x), idy=getid(y);
        if(vdep[idx]<vdep[idy]) swap(idx,idy), swap(x,y);
        if(vdep[idx]!=vdep[idy]) {
            if(x!=rt3[idx]) {
                ans+=calc_dis(rt2[idx],kth(rt2[idx],x-bg[idx]+1));
                x=rt3[idx];
            }
            int d=vdep[idx]-vdep[idy]-1;
            for(int i=0;i<=18;i++) {
                if(!(d&(1<<i))) continue;
                ans+=vdis[idx]-vdis[vfa[idx][i]];
                idx=vfa[idx][i]; x=rt3[idx];
            }
            ++ans; x=vofa[idx]; idx=vfa[idx][0];
        }
        if(idx!=idy) {
            if(x!=rt3[idx]) {
                ans+=calc_dis(rt2[idx],kth(rt2[idx],x-bg[idx]+1));
                x=rt3[idx];
            }
            if(y!=rt3[idy]) {
                ans+=calc_dis(rt2[idy],kth(rt2[idy],y-bg[idy]+1));
                y=rt3[idy];
            }
            for(int i=18;i>=0;i--) if(vfa[idx][i]!=vfa[idy][i]) {
                ans+=vdis[idx]-vdis[vfa[idx][i]]+vdis[idy]-vdis[vfa[idy][i]];
                idx=vfa[idx][i], idy=vfa[idy][i], x=rt3[idx], y=rt3[idy];
            }
            ans+=2; x=vofa[idx], y=vofa[idy]; idx=vfa[idx][0], idy=vfa[idy][0];
        }
        if(x>n) ans+=calc_dis(kth(rt2[idx],x-bg[idx]+1),kth(rt2[idy],y-bg[idy]+1));
        else ans+=calc_dis(x,y);
        W(ans); putchar('\n');
    }
}