24/02/21 染色问题

Iictiw / 2024-02-22 / 原文

题目描述

给定一棵 $n$ 个节点的树，你想把编号为 $i$ 的叶子节点染成 $a_i$ 的颜色。

你本来可以一个节点一个节点的涂，但你觉得这样太慢了，你决定这样染色：

选择一个节点 $x$ 和一种颜色 $c$，然后把这个颜色的颜料桶直接倒在节点 $x$ 上，使 $x$ 的所有子树都染成 $c$ 的颜色。

注意一个节点可以被染色多次，现在你想知道你最少需要染色几次。

输入格式

第一行一个正整数 $n$，表示树的节点数量。

第二行 $n-1$ 个整数 $f_i$ ，表示节点 $i+1$ 的父亲。

第三行 $n$ 个整数，若节点 $i$ 不是叶子节点，则 $a_i=0$，否则含义如题。

输出格式

一行一个整数，表示答案。

数据范围与提示

对于所有数据，$n \leq 5 \times 10^5 , f_i \in [1,i) , a_i \in [1,n]$ 。

子任务编号	数据范围	分值
1	$n \leq 8$	$15$
2	$n \leq 5 \times 10^3$	$45$
3	$n \leq 10^5$	$20$
4	$n \leq 5 \times 10^5$	$20$

这玩意是 dsu on tree 优化树形 DP ？？？

这是什么神奇的东西？

由于后染会覆盖先染，所以肯定是从根节点开始染色，于是乎就可以从根节点 DP。

设 $f_{x,i}$ 表示在以 $x$ 为根的子树中，先在 $x$ 上染上颜色 $i$ 之后，使得以 $x$ 为根的子树满足条件的最小代价。

首先肯定要在 $x$ 上染一次，所以 $f_{x,i}$ 初始为 $1$。

然后考虑 $x$ 的每个儿子 $y$ ，有两种可能，一种是由 $f_{y,i}$ 转移至 $f_{x,i}$ ，这样染完 $x$ 就不用再染一遍 $y$ 了，代价可以减 $1$。

其他情况下，就需要染完 $x$ 后再染 $y$。

于是就有

\[ f_{x,i} = \sum_{y \in \operatorname{son}(x)} ( \min^{n}_{j = 1} \begin{cases} f_{y,i} ,& i = j\\ f_{y,i}+1 ,& \text{otherwise.} \end{cases} - 1 ) + 1\]

这个东西直接做会是 $\Theta(n^3)$ 的，但是可以发现 $f_{x,i}$ 要么取 $f_{y,i}$ ，要么取 $f_{y,j},j \in [1,n]$ 中最小的那个。

所以可以DP时一并处理出 $f_{x,i}$ 的最小值，这样就是 $\Theta(n^2)$ 的了。

然而，最后求出的答案一定会在 $1$ 节点上染一次色，万一最后的答案不在 $1$ 上染呢？

……

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=5e3+5,inf=1e9+5;
int n,a[N];
vector<int> v[N];
int f[N][N],g[N];
void dfs(int p){
    if(a[p]){
        for(int i=1;i<=n;i++)f[p][i]=inf;
        f[p][a[p]]=1,g[p]=a[p];//叶子节点显然只会染 a[p]
        return;
    }
    for(auto to:v[p])dfs(to);
    for(int i=1;i<=n;i++){
        f[p][i]=1;
        for(auto to:v[p])
            f[p][i]+=min(f[to][i],f[to][g[to]]+(g[to]!=i))-1;
    }
    g[p]=1;
    for(int i=1;i<=n;i++)if(f[p][i]<f[p][g[p]])g[p]=i;//g[p] 为使 f[p][i] 最小的 i
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=2,x;i<=n;i++)cin>>x,v[x].push_back(i);
    for(int i=1;i<=n;i++)cin>>a[i];
    dfs(1);
    int ans=inf;
    for(int i=1;i<=n;i++)ans=min(ans,f[1][i]);//想一想，为什么这样是对的
    cout<<ans<<endl;
    return 0;
}

现在就有高贵的 60 pts 了。

注意到一件事实：转移时，许多颜色 $i$ 是无效的，比如在子树中尚未出现的颜色，它们对转移不会起到任何帮助。

我们就可以将这些无用的颜色一视同仁，看作同一种颜色。

那我们就可以将子节点的答案合并到父亲上了？

然后套上板子就好了？

当然不行啊。

一个 $O(n)$ 的转移拿头合并啊。

写出来估计也是个 $\Theta(n^2logn)$ 的废物。

而且可能存在不选根节点的情况，转移正确性也不保准……吗？

要是不对，估计也拿不到那 60pts 吧（笑。

稍微想一想，会发现给根节点提前染色一定不劣于其他方案。

严格证明我不会，可以感性理解一下。

首先给根节点染色一定是染一种和叶子颜色相同的颜色，要不不如不染。

由于后染的可以覆盖先染的，就可以把染的颜色不一样的看成没染，按正常的方案染上就好。

反正有了这个性质，我们原来做法的正确性就有了

回来观察一下原来的 DP 形式：

\[ f_{x,i} = \sum_{y \in \operatorname{son}(x)} ( \min^{n}_{j = 1} \begin{cases} f_{y,i} ,& i = j\\ f_{y,i}+1 ,& \text{otherwise.} \end{cases} - 1 ) + 1\]

记 $g_x = \min^{n}_{j = 1} f_{x,j}$ 那么就有

\[f_{x,i} = \sum_{y \in \operatorname{son}(x)} \min^{n}_{j = 1} ( g_y,f_{y,i} - 1 )+ 1 \]

如果 $f_{x,i} > g_x $ ，那 $f_{x,i}$ 就比不上 $g_x$ 了。

也就是说，只有 $f_{x,i} = g_x $ 的 $f_{x,i}$ 有意义。（根据定义，有 $f_{x,i} \geq g_x $）。

那我们只维护 $f_{x,i} = g_x $ 的 $i$ 就好了，用一个 vector 或是 map 把它们都存起来。

每次合并时如果有 $f_{x,i} > g_x $ ，就暴力把这些 $i$ 给删掉。

这样就是 $\Theta(nlogn)$ 的了。

代码实现

#include<iostream>
#include<cstdio>
#include<vector>
#include<unordered_map>
using namespace std;
using ll=long long;
const int N=5e5+5;
int n,a[N];
vector<int> v[N];
int sz[N],hson[N];
void dfs(int p){
    sz[p]=1;
    for(auto to:v[p]){
        dfs(to);
        sz[p]+=sz[to];
        if(sz[to]>sz[hson[p]])hson[p]=to;//找重儿子
    }
}
int f[N],id[N],tot;
unordered_map<int,int>mp[N];//偷了懒，用umap来存储
void redfs(int p){
    if(hson[p]){//先遍历重儿子
        redfs(hson[p]);
        id[p]=id[hson[p]],f[p]=f[hson[p]];
    }
    else{//是叶子节点，初始化边界
        id[p]=++tot;
        mp[id[p]][a[p]]=1,f[p]=1;
    }
    int mx=-1;
    for(auto to:v[p]){
        if(to==hson[p])continue;
        redfs(to);
        f[p]+=f[to];
        for(auto it=mp[id[to]].begin();it!=mp[id[to]].end();it=next(it)){
            int x=(*it).first;
            if(mp[id[p]].count(x))mx=max(mx,++mp[id[p]][x]);//有 i 优于其他答案了
            else mp[id[p]][x]=1;//标记f[x][i]=g[x]的 i
        }
    }
    if(mx!=-1){//如果有 f[x][i] 优于别人，或者说有 f[x][i] 劣于 g[x]了
        f[p]-=mx-1;//答案去掉劣的部分
        for(auto it=mp[id[p]].begin();it!=mp[id[p]].end();){
            if((*it).second<mx){//f[x][i] 不如 g[x]
                auto it2=it;it=next(it);
                mp[id[p]].erase(it2);//去掉 f[x][i]
            }
            else{   
                mp[id[p]][(*it).first]=1;//f[x][i]依然可以用
                it=next(it);
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(int i=2,x;i<=n;i++)cin>>x,v[x].push_back(i);
    for(int i=1;i<=n;i++)cin>>a[i];
    dfs(1);
    redfs(1);
    cout<<f[1]<<endl;
    return 0;
}
//iictiw-marisa