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

· · 题解

考虑朴素的 dp。不妨记 f_{i,j} 表示以 i 为根节点的子树内，到所有的叶子的黑色点个数为 j 最少需要选择多少个节点。转移是显然的，这样和树形背包复杂度是基本相同的，复杂度为 O(n^2)，在随机情况下复杂度为 O(n\log n)。

然后考虑优化。观察能得出对于每个 i，把所有点 (j,f_{i,j}) 画到坐标系上，发现这是一个凸函数。感性理解是简单的，具体证明可以直接归纳，是不难的。然后就可以直接闵可夫斯基和了。

但是又不想写闵可夫斯基和，这时候发现这个凸包在第一维是连续的。所以可以考虑用 slope trick 来维护转移。所以对每个点的答案就是前缀的一段负数斜率加上 f_{i,0}。然后考虑根节点颜色的影响，实际上相当于在其中插入一个 1/-1 的斜率，这个很好理解，就是改变根节点的颜色会让黑色点个数 +/-1，同时操作数也会变化 1，体现到斜率上就是 1/-1 的斜率。

所以可以直接用堆维护斜率，或者用两个数组分别维护正的斜率和负的斜率，再用一个变量维护 0 斜率的个数。时间复杂度取决于实现为单 \log 或线性。

#include<bits/stdc++.h>
using namespace std;
#define __MY_TEST__ 0
inline int read()
{
    int t;
    cin>>t;
    return t;
}
const int N=1e5+5;
char col[N];
int sze[N],f[N];
vector<int>gra[N];
priority_queue<int,vector<int>,greater<int> >q[N];
void dfs(int u)
{
    for(auto v:gra[u])
    {
        dfs(v);
        sze[u]+=sze[v];
        if(q[u].empty()) swap(q[u],q[v]),f[u]=f[v];
        else
        {
            priority_queue<int,vector<int>,greater<int> >ts;
            f[u]=0;
            while(!q[u].empty()&&!q[v].empty())
            {
                int tmp=q[u].top()+q[v].top();
                q[u].pop(),q[v].pop();
                if(tmp<0) f[u]+=tmp;
                ts.push(tmp);
            }
            q[u]=ts;
        }
    }
    if(col[u]=='0') q[u].push(1);
    else q[u].push(-1),sze[u]++,f[u]--;
}
void work()
{
    int n=read();
    for(int i=1;i<=n;i++) gra[i].clear(),sze[i]=f[i]=0;
    for(int i=1;i<=n;i++) while(!q[i].empty()) q[i].pop();
    cin>>col+1;
    for(int i=2;i<=n;i++) gra[read()].push_back(i);
    dfs(1);
    for(int i=1;i<=n;i++)
    {
        cout<<sze[i]+f[i];
        if(i<n) cout<<' ';
    }
    cout<<'\n';
}
signed main(){
#if __MY_TEST__
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t=read();
    while(t--) work();
}