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

· · 题解

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

博客园：[ROIR 2024] 树根 (Day 1) 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

树剖，线段树，二分。

分析

首先可以想到二分上界 lim，那么我们贪心地从深度最大的节点开始遍历，如果深度 >lim+1，就暴力地往上找 lim-1 级祖先，然后和根连一条额外的边。一直重复上述过程直到所有点深度都 \le lim+1。过程中我们连的边就是最少的，可以用于检查合法性。

暴力求解单次是 O(nk\log{n}) 的。

考虑优化，上数据结构，用线段树换根维护，那么过程中需要用到求换根后 k 级祖先，子树覆盖，这些都是比较套路的树上题目。

那么复杂度优化到了单次 O(k\log^2{n})，那么总复杂度 O(nk\log^2{n})。

最后一个优化，发现相邻点的答案之差不超过 1，那么我们维护一个类似双指针的东西，可以优化到 O(nk\log{n})。

代码

constexpr int N(2e5+10);

int n,m,idx,TYPE;
int fa[N],dl[N],dr[N],dfn[N],dep[N],siz[N],son[N],top[N];
vector<int> g[N];

void DFS0(int u) {
    dep[u]=dep[fa[u]]+1,siz[u]=1,son[u]=0;
    for(int v:g[u])if(v^fa[u])fa[v]=u,DFS0(v),siz[u]+=siz[v],son[u]=(siz[v]>siz[son[u]]?v:son[u]);
}

void DFS1(int u) {
    dfn[dl[u]=++idx]=u;
    if(son[u])top[son[u]]=top[u],DFS1(son[u]);
    for(int v:g[u])if(v!=fa[u]&&v!=son[u])DFS1(top[v]=v);
    dr[u]=idx;
}

struct SEG {
    struct node {
        int val,pos,tag;
        node(int val=0,int pos=0,int tag=0):val(val),pos(pos),tag(tag) {}

        void down(int _tag) { val+=_tag,tag+=_tag; }
    } tr[N<<2];
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
    void Up(int p) {
        int q(tr[ls].val>=tr[rs].val?ls:rs);
        tr[p].val=tr[q].val,tr[p].pos=tr[q].pos;
    }

    void Down(int p) { if(tr[p].tag)tr[ls].down(tr[p].tag),tr[rs].down(tr[p].tag),tr[p].tag=0; }

    void Build(int p=1,int l=1,int r=n) {
        tr[p]=node();
        if(l==r)return tr[p]=node(dep[dfn[l]],dfn[l]),void();
        Build(ls,l,mid),Build(rs,mid+1,r),Up(p);
    }

    void Plus(int L,int R,int d,int p=1,int l=1,int r=n) {
        if(L<=l&&r<=R)return tr[p].down(d);
        Down(p);
        if(L<=mid)Plus(L,R,d,ls,l,mid);
        if(mid<R)Plus(L,R,d,rs,mid+1,r);
        Up(p);
    }
#undef ls
#undef rs
#undef mid
} seg;

int lca(int u,int v) {
    for(; top[u]^top[v]; v=fa[top[v]])if(dep[top[u]]>dep[top[v]])swap(u,v);
    return dep[u]<dep[v]?u:v;
}

int anc(int u,int k) {
    int d(dep[u]-k);
    while(dep[top[u]]>d)u=fa[top[u]];
    return dfn[dl[top[u]]+d-dep[top[u]]];
}

int Anc(int rt,int u,int k) {
    int pa(lca(rt,u));
    return dep[u]-k>=dep[pa]?anc(u,k):anc(rt,dep[u]+dep[rt]-(dep[pa]<<1)-k);
}

int Lcs(int u,int pa) { return anc(u,dep[u]-dep[pa]-1); }

void Plus(int rt,int u,int d) {
    if(rt==u)return seg.Plus(1,n,d);
    if(dl[u]<=dl[rt]&&dr[rt]<=dr[u]) {
        int v(Lcs(rt,u));
        return seg.Plus(1,n,d),seg.Plus(dl[v],dr[v],-d);
    }
    return seg.Plus(dl[u],dr[u],d);
}

bool Check(const int rt,const int lim) {
    static int top(0),st[N];
    FOR(i,1,m) {
        if(seg.tr[1].val-1<=lim)break;
//      DE(rt,lim,i,seg.tr[1].pos);
//      DE(Anc(rt,seg.tr[1].pos,lim-1));
        Plus(rt,st[++top]=Anc(rt,seg.tr[1].pos,lim-1),-n);
    }
    bool ans(seg.tr[1].val-1<=lim);
    while(top)Plus(rt,st[top--],n);
    return ans;
}

int ans[N];

void DFS(int u) {
    if(u!=1) {
        while(!Check(u,ans[u]))++ans[u];
        while(ans[u]>1&&Check(u,ans[u]-1))--ans[u];
    }
    for(int v:g[u])if(v^fa[u]) {
        seg.Plus(1,n,1),seg.Plus(dl[v],dr[v],-2);
        ans[v]=ans[u],DFS(v);
        seg.Plus(dl[v],dr[v],2),seg.Plus(1,n,-1);
    }
}

signed main() {
#ifdef plus_cat
    freopen(plus_cat ".in","r",stdin),freopen(plus_cat ".out","w",stdout);
#endif // plus_cat
    /*DE("Input");*/
    I(n,m,TYPE);
    if(m>=n-1) {
        if(!TYPE)return puts("1"),0;
        FOR(i,1,n)O(1,' ');
        return puts(""),0;
    }
    FOR(i,2,n) {
        int u,v;
        I(u,v),g[u].push_back(v),g[v].push_back(u);
    }
    /*DE("Build");*/
    DFS0(1),DFS1(top[1]=1),seg.Build();
    /*DE("Solve");*/
    ans[1]=n-1;
    for(int l(1),r(n-1),mid((l+r)>>1); l<=r; mid=(l+r)>>1)Check(1,mid)?ans[1]=mid,r=mid-1:l=mid+1;
    if(!TYPE)return O(ans[1],'\n'),0;
    DFS(1);
    /*DE("Output");*/
    FOR(i,1,n)O(ans[i],' ');
    return puts(""),0;
}