题目描述
给定一棵 \(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