这道题的思路很简单,就是子树缩成大点,之后跑lca求距离就好了。

如果我们要跳lca的话,那么就要记录一个大点到另外一个大点的信息了。

大概就是记录一下每一个大点管辖的节点区间,表示哪科子树,挂着这个大点的在模板树下是哪个小节点,便于跳上去。

因为询问和添加都是给定一个小点的编号,

因此需要二分去查询小点所在的大点编号,以及小点在模板树表示哪个节点,这样方便跳。

询问的时候,要注意细节:

如果两小点在同一大点上,直接求。

否则先把一个小点挪到当前大点的根上,再倍增跳。

另外一个小点先不要动,因为在路径是一条链的时候,它不一定要挪到根上。

总之就是,两小点要最后到同一大点上,之后跑到模板树上算。

由于变量名匮乏,开了两个名空间。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#define gc getchar()
#define ll long long
#define ld long double 
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=4e5+5;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
template<class o>
void qw(o x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int n,m,Q;
struct HJTSeg
{
    struct Seg{int s,l,r;}t[N<<5];int cnt,root[N];
    void modify(int l,int r,int &x,int y,int pos)
    {
        t[x=++cnt]=t[y];++t[x].s;
        if(l==r)return ;
        int mid=l+r>>1;
        if(pos<=mid)modify(l,mid,t[x].l,t[y].l,pos);
        else modify(mid+1,r,t[x].r,t[y].r,pos);
    }
    int query(int l,int r,int x,int y,int k)
    {
        if(l==r)return l;
        int sum=t[t[x].l].s-t[t[y].l].s,mid=l+r>>1;
        if(sum>=k)return query(l,mid,t[x].l,t[y].l,k);
        return query(mid+1,r,t[x].r,t[y].r,k-sum);
    }
}H;
namespace pretree
{
    struct edge{int y,next;}a[N<<1];int len,last[N],cnt;
    void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
    int fa[N][18],d[N][18],dfn[N],yss[N],dep[N],low[N],siz[N];
    void dfs(int x)
    {
        dfn[x]=++cnt;yss[cnt]=x;siz[x]=1;
        for(int i=1;i<18;i++)
            fa[x][i]=fa[fa[x][i-1]][i-1],
            d[x][i]=d[x][i-1]+d[fa[x][i-1]][i-1];
        for(int k=last[x],y;k;k=a[k].next)
        {
            if((y=a[k].y)==fa[x][0])continue;
            fa[y][0]=x;dep[y]=dep[x]+1;d[y][0]=1;
            dfs(y);
            siz[x]+=siz[y];
        }
        low[x]=cnt;//子树结尾 
    }
    void init()
    {
        qr(n),qr(m),qr(Q);
        for(int i=1,x,y;i<n;i++)qr(x),qr(y),ins(x,y),ins(y,x);
        dep[1]=1;fa[1][0]=0;
        dfs(1);
        for(int i=1;i<=n;i++)H.modify(1,n,H.root[i],H.root[i-1],yss[i]);
    }
    int query(int x,int y)
    {
        int ans=0;
        if(dep[x]<dep[y])swap(x,y);
        for(int i=17;~i;i--)
            if(dep[fa[x][i]]>=dep[y])ans+=d[x][i],x=fa[x][i];
        if(x==y)return ans;
        for(int i=17;~i;i--)
            if(fa[x][i]!=fa[y][i])ans+=d[x][i]+d[y][i],x=fa[x][i],y=fa[y][i];
        return ans+d[x][0]+d[y][0];
    }
    int get_id(int x,ll k)
    {
        return H.query(1,n,H.root[low[x]],H.root[dfn[x]-1],(int)k);
    }
    int dis(int x,int y){return dep[x]-dep[y];}
}
namespace bigtree
{
    ll link[N],S[N],T[N];int bel[N],cnt;//LINK 大节点上面那个点是哪个小点;BEL 大节点表示哪个子树。
    int fa[N][18],dep[N];ll d[N][18];//d表示从根到根的距离
    int findbig(ll x)
    {
        int l=1,r=cnt;
        while(l<r)
        {
            int mid=l+r+1>>1;
            if(S[mid]>x)r=mid-1;
            else l=mid;
        }
        return l;
    }
    int findsmall(int p,ll x)
    {
        return pretree::get_id(bel[p],x-S[p]+1);
    }
    void build()
    {
        cnt=1;S[1]=1;T[1]=n;bel[1]=1;link[1]=0;fa[1][0]=0;dep[1]=1;
        for(int i=1;i<=m;i++)    
        {
            ll x,y;qr(y),qr(x);int p=findbig(x),q=findsmall(p,x);
            link[++cnt]=x;S[cnt]=T[cnt-1]+1;T[cnt]=S[cnt]+pretree::siz[y]-1;bel[cnt]=y;
            fa[cnt][0]=p;d[cnt][0]=1+pretree::dis(q,bel[p]);dep[cnt]=dep[p]+1;
            for(int i=1;i<=17;i++)
                fa[cnt][i]=fa[fa[cnt][i-1]][i-1],
                d[cnt][i]=d[cnt][i-1]+d[fa[cnt][i-1]][i-1];
        }
    }
    ll query(ll x,ll y)
    {
        ll ans=0;
        int u1=findbig(x),v1=findsmall(u1,x);
        int u2=findbig(y),v2=findsmall(u2,y);
        if(u1==u2)return pretree::query(v1,v2);
        if(dep[u1]<dep[u2])swap(u1,u2),swap(v1,v2);
        ans+=pretree::dis(v1,bel[u1]);
        //v1=bel[u1],v2=bel[u2];
        for(int i=17;~i;i--)
            if(dep[fa[u1][i]]>=dep[u2]&&fa[u1][i]!=u2)ans+=d[u1][i],u1=fa[u1][i];
        if(dep[u1]==dep[u2])
        {
            ans+=pretree::dis(v2,bel[u2]);
            for(int i=17;~i;i--)
                if(fa[u1][i]!=fa[u2][i])ans+=d[u1][i]+d[u2][i],u1=fa[u1][i],u2=fa[u2][i];
            ans+=2;v1=findsmall(fa[u1][0],link[u1]),v2=findsmall(fa[u2][0],link[u2]);
            ans+=pretree::query(v1,v2);
            return ans;
        }
        ans++;v1=findsmall(u2,link[u1]);
        return ans+pretree::query(v1,v2);
    }
    void solve()
    {
        while(Q--)
        {
            ll x,y;qr(x),qr(y);
            qw(query(x,y));puts("");
        }
    }
}
int main()
{    
    //freopen("tree2.in","r",stdin);
    pretree::init();
    bigtree::build();
    bigtree::solve();
    return 0;
}