题解：P15370 『ICerOI Round 1』这是兔兔，她很可爱

· · 题解

骡的岛……

初步转化

问题可以初步转化为对于路径上一点 x，是否有不少于 k 个值小于等于它。观察到第 k 大，而我们相对位置也是根据路径上的先后关系来决定的，所以我们不妨考虑二分答案。

我们再考虑这个相对位置是怎么求的，不妨把 u\to v 路径分成三个部分：

那么现在就有一个瓶颈——如何快速求出一子树内编号在 [l,r] 的个数？

完整解法

我们想到将树利用 dfs 序拍成一个序列。定义 dfn_u 表示 u 的 dfs 序，然后 siz_u 表示以 u 为根的子树节点数量，那么我们实际上子树查询就是在序列 [dfn_u,dfn_u+siz_u-1] 这个区间内查询编号在 [l,r] 内的点，可以用主席树维护。

还有一个点，就是在 lca\to u 的部分，怎么快速处理出 next_x。实际上很简单，因为我们二分的是路径上的点距离起点的距离，我们可以利用倍增求 lca 的思想。可以很简单的求出 x 是 u 或 v 的几级祖先，然后倍增跳上去即可。

时间复杂度的话就是 \mathcal O(n\log^2 n)，阿米娅女鹅怎么这么卡常……

贴一下我的代码喵：

constexpr int N=2e5+5;
int n,q,l,r,u,v,k,lst;
class Nygglatho{
public:
    int cnt=2;
    int head[N],to[2*N],nt[2*N];
    void addedge(int u,int v){
        to[cnt]=v,nt[cnt]=head[u],head[u]=cnt++;
        to[cnt]=u,nt[cnt]=head[v],head[v]=cnt++;
    }
}E;

constexpr int L=19;
int tim;
int dfn[N],dep[N],siz[N],rev[N],fa[N][L];
void dfs(int u,int fath){
    fa[u][0]=fath,dep[u]=dep[fath]+1,siz[u]=1,dfn[u]=++tim,rev[tim]=u;
    for(int i=1;i<L;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=E.head[u];i;i=E.nt[i]){
        int v=E.to[i];
        if(v==fath) continue;
        dfs(v,u);
        siz[u]+=siz[v];
    }
}
int getlca(int x,int y){
    if(dep[x]>dep[y]) swap(x,y);
    int tmp=dep[y]-dep[x];
    for(;tmp;){
        int i=__builtin_ctzll(tmp);
        tmp&=(tmp-1);
        y=fa[y][i];
    }
    if(x==y) return y;
    for(int i=L-1;i>=0;i--) if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
    return fa[y][0];
}
int getkth(int x,int k){
    for(;k;){
        int i=__builtin_ctzll(k);
        k&=(k-1);
        x=fa[x][i];
    }
    return x;
}

int cnt;
int rt[N],tr[N*L],ls[N*L],rs[N*L];
int update(int pre,int x){
    int rt=++cnt,cur=rt,l=1,r=n;
    tr[cur]=tr[pre]+1,ls[cur]=ls[pre],rs[cur]=rs[pre];
    for(;l<r;){
        int mid=(l+r)>>1;
        if(x<=mid){
            ls[cur]=++cnt;
            cur=ls[cur],pre=ls[pre];
            r=mid;
        }else{
            rs[cur]=++cnt;
            cur=rs[cur],pre=rs[pre];
            l=mid+1;
        }
        tr[cur]=tr[pre]+1,ls[cur]=ls[pre],rs[cur]=rs[pre];
    }
    return rt;
}
int intersum(int u,int v,int ql,int qr){
    if(!u&&!v) return 0;
    int su[64],sv[64],sl[64],sr[64],stop=0;
    su[0]=u,sv[0]=v,sl[0]=1,sr[0]=n;
    int ans=0;
    for(int i=0;i<=stop;i++){
        int cu=su[i],cv=sv[i],cl=sl[i],cr=sr[i];
        if(!cu&&!cv) continue;
        if(ql<=cl&&cr<=qr){ ans+=tr[cv]-tr[cu]; continue; }
        int mid=(cl+cr)>>1;
        if(ql<=mid){ ++stop,su[stop]=ls[cu],sv[stop]=ls[cv],sl[stop]=cl,sr[stop]=mid; }
        if(qr>mid){ ++stop,su[stop]=rs[cu],sv[stop]=rs[cv],sl[stop]=mid+1,sr[stop]=cr; }
    }
    return ans;
}

int check(int k,int u,int v,int lca,int L,int R,int len,int dis_u){
    if(k<=dis_u){
        int x=getkth(u,k-1);
        return intersum(rt[dfn[x]-1],rt[dfn[x]+siz[x]-1],L,R);
    }
    if(k<len){
        int x=getkth(v,len-k-1);
        return R-L+1-intersum(rt[dfn[x]-1],rt[dfn[x]+siz[x]-1],L,R);
    }
    return R-L+1;
}
int binary_answer(int u,int v,int L,int R,int k){
    int lca=getlca(u,v);
    int len=dep[u]+dep[v]-2*dep[lca]+1;
    int dis_u=dep[u]-dep[lca];
    if(check(1,u,v,lca,L,R,len,dis_u)>=k) return u;
    int l=2,r=len,ans=len;
    for(;l<=r;){
        int mid=(l+r)>>1;
        if(check(mid,u,v,lca,L,R,len,dis_u)>=k) ans=mid,r=mid-1;
        else l=mid+1;
    }
    if(ans<=dis_u) return getkth(u,ans-1);
    return getkth(v,len-ans);
}

signed main(){
    n=read(),q=read();
    for(int i=1;i<n;i++){
        u=read(),v=read();
        E.addedge(u,v);
    }
    dfs(1,0);
    for(int i=1;i<=n;i++) rt[i]=update(rt[i-1],rev[i]);
    for(;q--;){
        l=read(),r=read(),u=read(),v=read(),k=read();
        l^=lst,r^=lst,u^=lst,v^=lst,k^=lst;
        lst=binary_answer(u,v,l,r,k);
        write(lst),writec('\n');
    }
    chtholly();
}