萌新提问
查看原帖
萌新提问
297420
春待ち青鸟楼主2020/5/18 14:06
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=100005;
int n,m,Q,tot,firs[N],nex[N<<1],to[N<<1];
inline void add(int u,int v){
    to[++tot]=v;
    nex[tot]=firs[u];
    firs[u]=tot;
}
int S[N],tat,f[N][22],dep[N],q[N],T[N];
struct node{
    int rt[N],tot;
    int L[N*20],R[N*20],s[N*20];
    inline int built(int l,int r){
        int rt=++tot,mid=(l+r)>>1;
        if(l>=r)return rt;
        L[rt]=built(l,mid);
        R[rt]=built(mid+1,r);
        return rt;
    }
    inline int add(int x,int pre,int l,int r){
        int rt=++tot,mid=(l+r)>>1;
        L[rt]=L[pre];R[rt]=R[pre];s[rt]=s[pre]+1;
        if(l>=r)return rt;
        if(x<=mid)L[rt]=add(x,L[pre],l,mid);
        else R[rt]=add(x,R[pre],mid+1,r);
        return rt;
    }
    inline int query(int x,int y,int k,int l,int r){
        int mid=(l+r)>>1,z=(s[L[y]]-s[L[x]]);
        if(l==r)return mid;
        if(z>=k)return query(L[x],L[y],k,l,mid);
        else return query(R[x],R[y],k-x,mid+1,r);
    }
}zxs;
inline void dfs(int x,int fa){
    S[x]=++tat;
    q[tat]=x;
    f[x][0]=fa;dep[x]=dep[fa]+1;
    for(int i=1;i<=16;++i)f[x][i]=f[f[x][i-1]][i-1];
    for(int i=firs[x];i;i=nex[i]){
        int y=to[i];
        if(y==fa)continue;
        dfs(y,x);
    }T[x]=tat;
}
inline long long lca(int x,int y){
    long long ans=0;
    if(dep[x]<dep[y])swap(x,y);
    for(int i=16;i>=0;--i)if(dep[f[x][i]]>=dep[y]){
        ans+=(1<<i);
        x=f[x][i];
    }if(x==y)return ans;
    for(int i=16;i>=0;--i){
        if(f[x][i]!=f[y][i]){
            x=f[x][i];
            y=f[y][i];
            ans+=(1<<(i+1));
        }
    }return ans+2;
}
namespace work{
    int tot=1,fa[N][22],dp[N],pre[N];
    long long SS[N],TT[N],firs[N],cnt,dis[N][22];
    inline int find(long long x){
        int l=1,r=tot,mid;
        while(l<=r){
            mid=(l+r)>>1;
            if(SS[mid]<=x)l=mid+1;
            else r=mid-1;
        }return r;
    }
    inline int Pre(long long x){
        int rt=find(x);
        return zxs.query(zxs.rt[S[pre[rt]]-1],zxs.rt[T[pre[rt]]],x-SS[rt]+1,1,n);
    }
    void init(){
        dp[1]=1;pre[1]=1,SS[1]=1,TT[1]=n;cnt=TT[1];
        for(int i=1;i<=m;++i){
            int qi;long long ho;
            scanf("%d%lld",&qi,&ho);
            int rt=find(ho);
            ++tot;
            dp[tot]=dp[rt]+1;
            firs[tot]=ho;
            pre[tot]=qi; 
            SS[tot]=cnt+1;
            TT[tot]=cnt+T[qi]-S[qi]+1;cnt=TT[tot];
            fa[tot][0]=rt;
            dis[tot][0]=dep[Pre(ho)]-dep[pre[rt]]+1;//???
            for(int j=1;j<=16;++j)fa[tot][j]=fa[fa[tot][j-1]][j-1],dis[tot][j]=dis[tot][j-1]+dis[fa[tot][j-1]][j-1];
        }
    }
    inline long long work(long long u,long long v){
        long long ans=0;
        int x=find(u),y=find(v);
        if(x==y)return lca(Pre(u),Pre(v));
        if(dep[x]<dep[y]){
            swap(x,y);swap(u,v);
        }ans+=dep[Pre(u)]-dep[pre[x]];
        for(int i=16;i>=0;--i)if(dp[fa[x][i]]>dp[y]){
            ans+=dis[x][i];x=fa[x][i];
        }if(find(firs[x])==y){
            return ans+1+lca(Pre(firs[x]),Pre(v));
        }
        ans+=dep[Pre(v)]-dep[pre[y]];
        if(dp[x]>dp[y]){
            ans+=dis[x][0];
            x=fa[x][0];
        }
        for(int i=16;i>=0;--i)if(fa[x][i]!=fa[y][i]){
            ans+=dis[x][i];x=fa[x][i];ans+=dis[y][i];y=fa[y][i];
        }x=firs[x],y=firs[y];
        return ans+2+lca(Pre(x),Pre(y));
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&Q);
    int x,y;
    for(int i=1;i<n;++i){
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
    zxs.rt[0]=zxs.built(1,n);
    for(int i=1;i<=n;++i)zxs.rt[i]=zxs.add(q[i],zxs.rt[i-1],1,n);
    for(int i=1;i<=Q;++i){
        long long aa,bb;
        scanf("%lld%lld",&aa,&bb);
        printf("%lld\n",work::work(aa,bb));
    }
}
2020/5/18 14:06
加载中...