【题解】P11123 [ROIR 2024] 树根 (Day 1)

zhouxianzhuo · 2025-11-16 11:43:04 · 题解

考虑二分答案，思考如何判断一个答案是否可行。

假设当前需判断答案为 lim 是否可行。贪心的想，可以每次找到整棵树内最深的点 x，从根向 x 的 lim-1 级祖先 y 连边，这样整棵 y 的子树就都合法了，可以删掉这棵子树。

如此重复 k 次后，判最深的点的深度是否小于等于 lim，即可判断答案为 lim 是否可行。

查找整棵树内最深的点可以用线段树维护，而删去一棵子树相当于区间减 n，因为不存在点的深度超过 n，由此得判断一次的复杂度为 O(k\log n)。

接下来考虑相邻点换根对深度、树上 k 级祖先、子树的影响，设换根后的根为 rt。

• 换根后的深度是容易维护的，则只需将 rt 的子树减 1，其它点加 1 即可。

• 对于点 x，树上 k 级祖先需要分讨：

  设 l 为原树上 rt 和 x 的 lca。

  • 若 dis(l,x)\ge k，则 x 的树上 k 级祖先为原树上 x 的树上 k 级祖先。
  • 否则，x 的树上 k 级祖先为原树上 rt 的 dis(rt,x)-k 级祖先。

• 对于点 x，子树亦需分讨：

  • 若 rt=x，则 x 的子树为所有点。
  • 若在原树中，rt 在 x 的子树内，设 y 为 x 向 rt 方向的儿子，则此时 x 的子树为除原树中 y 的子树外的所有点。
  • 否则，x 的子树不变。

对于每个点都二分答案可以做到 O(nk\log^2n)，但还能更优。

发现换根后的答案变动不超过 1，因此换根时的判断次数可以缩至 O(1)，这样做的复杂度为 O(k\log^2 n+nk\log n)。

代码如下，具体看注释：

#include<bits/stdc++.h>
using namespace std;
struct opt{
    int l,r,v;
};
int n,k,t,son[200010],ans[200010];
int hd[200010],ne[400010],to[400010],tot;
int dp[200010],cnt,dfn[200010],rnk[200010],btm[200010],st[200010][25],lg[200010],jump[200010][25];
long long tag[800010];
pair<long long,int> tree[800010];
vector<opt> op;
void add(int x,int y){
    tot+=1;
    ne[tot]=hd[x];
    hd[x]=tot;
    to[tot]=y;
}
void dfs(int x,int fa){
    dp[x]=dp[fa]+1;
    cnt+=1;
    dfn[x]=cnt;
    rnk[cnt]=x;
    st[dfn[x]][0]=dfn[fa];
    jump[x][0]=fa;
    for(int i=1;i<=20;i++)
        jump[x][i]=jump[jump[x][i-1]][i-1];
    for(int i=hd[x];i>=1;i=ne[i])
    {
        if(to[i]==fa)continue;
        dfs(to[i],x);
    }
    btm[x]=cnt;
}
void init(){
    for(int i=2;i<=n;i++)
        lg[i]=lg[i>>1]+1;
    for(int j=1;j<=20;j++)
    {
        for(int i=1;i+(1<<j)-1<=n;i++)
            st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
    }
}
//预处理 st 表 
inline int ask(int l,int r){
    return min(st[l][lg[r-l+1]],st[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}
inline int lca(int x,int y){
    if(x==y)return x;
    if(dfn[x]>dfn[y])swap(x,y);
    return rnk[ask(dfn[x]+1,dfn[y])];
}
//st 表求原树中 x 和 y 的 lca 
inline int dis(int x,int y){
    return dp[x]+dp[y]-dp[lca(x,y)]*2;
}
//x 到 y 的距离 
int up(int x,int k){
    for(int i=0;i<=20;i++)
        if(k&(1<<i))x=jump[x][i];
    return x;
}
//原树中 x 的 k 级祖先 
int anc(int rt,int x,int k){
    if(dis(rt,x)<=k)return rt;
    int l=lca(rt,x);
    if(dis(l,x)>=k)return up(x,k);
    //树上 k 级祖先分讨 1 
    return up(rt,dis(rt,x)-k);
    //树上 k 级祖先分讨 2 
}
//根为 rt 时 x 的 k 级祖先 
inline void pushup(int x){
    tree[x]=max(tree[x*2],tree[x*2+1]);
}
inline void addtag(int x,long long v){
    tree[x].first+=v;
    tag[x]+=v;
}
inline void pushdown(int x){
    addtag(x*2,tag[x]);
    addtag(x*2+1,tag[x]);
    tag[x]=0;
}
void build(int l,int r,int x){
    if(l==r)
    {
        tree[x]={dp[rnk[l]]-1,rnk[l]};
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,x*2);
    build(mid+1,r,x*2+1);
    pushup(x);
}
void change(int l,int r,int x,int ll,int rr,int v){
    if(l>=ll&&r<=rr)
    {
        addtag(x,v);
        return;
    }
    pushdown(x);
    int mid=(l+r)>>1;
    if(ll<=mid)change(l,mid,x*2,ll,rr,v);
    if(rr>mid)change(mid+1,r,x*2+1,ll,rr,v);
    pushup(x);
}
//线段树维护整棵树深度最深的点 
bool check(int rt,int lim){
    int ts=k;
    while(ts>=1)
    {
        ts-=1;
        int x=tree[1].second;
        //x 为整棵树最深的点 
        int y=anc(rt,x,lim-1);
        //y 为 x 的 lim-1 级祖先 
        if(y==rt)return true;
        //子树分讨 1 
        if(son[y]==0)
        {
            change(1,n,1,dfn[y],btm[y],-n);
            op.push_back((opt){dfn[y],btm[y],-n});
        }
        //子树分讨 3 
        else
        {
            change(1,n,1,1,n,-n);
            change(1,n,1,dfn[son[y]],btm[son[y]],n);
            op.push_back((opt){1,n,-n});
            op.push_back((opt){dfn[son[y]],btm[son[y]],n});
        }
        //子树分讨 2 
    }
    if(tree[1].first<=lim)return true;
    return false;
}
void clear(){
    for(opt o:op)
        change(1,n,1,o.l,o.r,-o.v);
    op.clear();
}
//消除 check 对线段树的影响 
void dfs_ans(int x,int fa){
    int l,r;
    if(x==1)
    {
        l=0;
        r=n;
    }
    //当前根为 1 则进行 O(log n) 次二分 
    else
    {
        l=max(ans[fa]-2,0);
        r=ans[fa]+1;
    }
    //当前根不为 1 则由父亲的答案进行 O(1) 次二分 
    while(l+1<r)
    {
        int mid=(l+r)>>1;
        if(check(x,mid))r=mid;
        else l=mid;
        clear();
    }
    ans[x]=r;
    for(int i=hd[x];i>=1;i=ne[i])
    {
        if(to[i]==fa)continue;
        son[x]=to[i];
        //记录向 rt 方向的儿子 
        change(1,n,1,1,n,1);
        change(1,n,1,dfn[to[i]],btm[to[i]],-2);
        //换根对深度的影响 
        dfs_ans(to[i],x);
        change(1,n,1,1,n,-1);
        change(1,n,1,dfn[to[i]],btm[to[i]],2);
        //消除换根对深度的影响 
    }
    son[x]=0;
}
int main(){
    scanf("%d%d%d",&n,&k,&t);
    for(int i=1;i<=n-1;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
    init();
    build(1,n,1);
    dfs_ans(1,0);
    if(t==0)printf("%d",ans[1]);
    else
    {
        for(int i=1;i<=n;i++)
            printf("%d ",ans[i]);
    }
    return 0;
}