题解：P13954 [ICPC 2023 Nanjing R] 红黑树

· · 题解

前言

模拟赛遇到的，由于单调队列优化的时候，少些了一个限制，被神秘绑包和子任务依赖干成 0 分。不如暴力的 100 分。

提供一种仅使用单调队列的 O(n) 算法，但一些证明需要长剖的知识。

分析

暴力

直观地，设 dp_{u,k} 表示 u 子树内所有叶子节点到 u 的路径上均有 k 个黑色节点的最小修改数。

DP 的时候，现将子节点的结果对位加起来，再去考虑当前点是否改变颜色。

由于第二维最多是树高 h，复杂度 O(nh)。

优化

发现这个算法和深度相关，难道是长剖？然而每次选择的是最短链，不妨假装有一种叫做短链剖分的算法。

来具体地分析一下复杂度，记 v 到叶子节点的最短距离为 mnlen_v，记 u 节点的子节点个数为 \deg_u。

则在 u 处的代价为 \deg_u\times \min_{v\in son_u}mnlen_v。在一条链的情况下可以被卡到 O(n^2)。

如果 \deg_u\ge 2，则研究这种剖分方式和长剖的区别，我们发现：短链剖分的情况下，总操作次数不超过长剖链剖分的两倍。因为长儿子对应的链也被改成了 \min_{v\in son_u}mnlen_v。

然而，\deg_u=1 时，长剖单点开销为 O(1)，而短剖仍要 O(mnlen_v)，这是问题所在！

然而我们观察到：\deg_u=1 的点，其答案和其唯一子节点 v 相同。则可以先不更新它，把这些点放在一起更新，此时可以使用单调队列进行优化，复杂度不会变大。

那么捋一下思路：

这样，总复杂度即为长剖复杂度，做到 O(n)。

:::info[注] 如果你不会长剖，那么可以把 mnlen 放大成 mnsiz，这样复杂度不超过 dsu on tree，是 O(n\log{n})，在本题中已经足够了。 :::

实现

代码末尾的注释是一点烧烤过程，可忽略。

:::info[code]

#include<bits/stdc++.h>
using namespace std;

const int N=100005;
int n,rt,ans[N],dep[N],Q[N],tmp[N];
int col[N],len[N],fa[N],mp[N],ind[N];
vector<int>E[N],A[N];
//节点变得有长度
inline int read(){
    int a=0,c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) a=10*a+c-'0',c=getchar();
    return a;
}

inline void write(int x){
    int sk[20],top=0;
    do{
        sk[++top]=x%10,x/=10;
    }while(x);
    while(top) putchar(sk[top--]+'0');
    putchar(' ');
}

void rebuild(){//树要缩链
    for(int i=1;i<=n;i++){
        mp[i]=i,ind[i]=0,len[i]=1;
        E[i].clear(),A[i].clear();
    }
    for(int i=2;i<=n;i++) ind[fa[i]]++;
    for(int i=n;i>=2;i--){
        if(ind[fa[i]]!=1) continue;//可以消去
        mp[fa[i]]=mp[i],col[mp[i]]+=col[fa[i]];
        len[mp[i]]+=len[fa[i]],fa[mp[i]]=fa[fa[i]]; 
    }
    for(int i=1;i<=n;i++){
        if(mp[i]==i&&fa[i]!=0) E[fa[i]].emplace_back(i);
    }
    rt=mp[1];
}

inline void cmin(int &a,int b){(a>b)&&(a=b);}

inline void calc(int u,int mx,int to){
    int head=1,tail=1,c=col[u];
    while(A[u].size()<mx+1) A[u].emplace_back(N);//补齐长度，因为在 u 处没有补上 len，这里补一下
    for(int i=0;i<=mx;i++) tmp[i]=A[u][i]+c;//tmp 临时数组
    for(int i=c;i<=mx;i++){//单调队列优化
        while(head!=tail&&i-Q[head]>len[u]) head++;
        int j=i-c;
        while(head!=tail&&A[u][Q[tail-1]]-Q[tail-1]>=A[u][j]-j) tail--;
        Q[tail++]=j,cmin(tmp[i],A[u][Q[head]]-Q[head]+i-c);
    }
    head=tail=1,Q[tail++]=0;
    for(int i=1;i<=mx;i++){
        while(head!=tail&&i-Q[head]>=c) head++;
        if(head!=tail) cmin(tmp[i],A[u][Q[head]]+Q[head]+c-i);
        while(head!=tail&&A[u][Q[tail-1]]+Q[tail-1]>=A[u][i]+i) tail--;
        Q[tail++]=i;
    }
    for(int i=0;i<=mx;i++) A[to][i]+=tmp[i];
    A[u].clear();
}
//f_i=min(g_j-j)+i-c(i-j>=c&&i-j<=len) &&i-j<=len 是 100->0 的原因
//f_i=min(g_j+j)+c-i(i-j<c)
void dfs(int u){
    if(E[u].size()==0){//dep 就是 mnlen 
        dep[u]=len[u],A[u].emplace_back(0);
        return ans[u]=0,void();
    }
    dep[u]=N,ans[u]=N;
    for(auto &v:E[u]) dfs(v),cmin(dep[u],dep[v]);  
    A[u].resize(dep[u]+1);
    for(int i=0;i<=dep[u];i++) A[u][i]=0;
    for(auto &v:E[u]) calc(v,dep[u],u);
    for(int i=0;i<=dep[u];i++) cmin(ans[u],A[u][i]);
    dep[u]+=len[u];
}

void solve(){
    n=read();char c=getchar();
    while(!isdigit(c)) c=getchar();
    for(int i=1;i<=n;i++) col[i]=c-'0',c=getchar();
    for(int i=2;i<=n;i++) fa[i]=read();
    rebuild(),dfs(rt);
    for(int i=1;i<=n;i++) write(ans[mp[i]]);
}

int main(){
    // #ifdef LOCAL
    // #else
    // freopen("tree.in","r",stdin);
    // freopen("tree.out","w",stdout);
    // #endif
    // double st=clock();
    for(int Tcnt=read();Tcnt;Tcnt--){
        solve(),putchar('\n');
    }
    // fprintf(stderr,"%.5lf\n",(clock()-st)/CLOCKS_PER_SEC);
    return 0;
}
/*
可能是整体 DP？
长链剖分优化 DP？
不是很对啊，对长链的操作无法避免，还是要和树高相关，但可能是高分
除非每个点都有至少两个子节点，考虑单链的部分缩起来（同一条单链上的结果相同）
好像可以？
因为实际上只保留短链的长度，每个单链分两段用单调队列去计算，难写
corner 会很多
很难写啊，复杂度不会证，假定是对的
1
12 
111111110101 
1 1 2 3 2 5 1 8 4 8 3
4 1 1 0 0 0 0 0 0 0 0 0
*/
/*
复杂度分析：
缩点其实就是让单链上的点不被统计
每个点处贡献如下：
最短链*度数<=短儿子长度和+最短链（最长的一条仍认为被截断）<=2*短儿子长度和<=2*长剖意义下的短儿子长度和

*/

:::