作为最强摸鱼人的 BaiBaiShaFeng,这个题解也是发到洛谷上了,希望给过。
先辈们说的太简略了我感觉有点难懂,虽然我的表达能力很弱,估计强不了多少。
注:参考过网上零散题解。
题意很好理解,我们就不过多叙述了。
不看炸掉的机子,我们实际上是在选择一个联通块去覆盖树的一部分,而我们所要求的就是这个联通块的最大值。
我们统一在这个联通快的最高点进行答案的统计,从子树的贡献向上递归,这个样子问题可以从子树中合并上来,进而考虑树形 dp。
设 \(dp[u]\) 表示联通块的最高点还在祖先处时 \(u\) 子树中的答案,形象的说,就是上不封顶。
这个时候我们只要选择了 \(u\) 子树中的发电机 \(u\) 自然会炸,因为最高点在祖先,上边会有其他启动的发电机。
所以我们一共有两种决策:选择所有子树中的最佳情况或者干脆不选子树,去选 \(u\) 上的发电机。
注意如果没有发电机便只有第一种情况。
明显不存在其他情况。
转移于是乎就明显起来了,我们在 \(\sum_{v\in son[u]} dp[v]-1\) 和 \(1\) 之间取最大就是 \(dp[u]\) 了。
这个式子对应了我们上边说的两种情况,下边说说答案的统计。
我们规定了在最高点统计答案,每个点都可以是最高点,对于一个最高点,若不想让这个点炸只能选择一个子树中的答案,若允许它炸就直接选择所有子树中的答案再让它炸,第二种和 \(dp[u]\) 最终的结果应该是相等的,但是含义并不一样,后边为了方便写在一起了。
代码如下,这个题想起来有些麻烦但实现起来就很轻松。
#include <bits/stdc++.h>
using namespace std;
const int MN=1e6+116;
struct Node{int nxt, to;
}node[MN];
int head[MN], tottt;
void insert(int u, int v){node[++tottt].to=v;node[tottt].nxt=head[u];head[u]=tottt; return;
}
//以上是平平无奇的存图
int n, dp[MN], has[MN], ans=0;//has表示介个点有没有发电机
void Read(){memset(dp,0,sizeof(dp)); memset(has,false,sizeof(dp));cin>>n;for(int i=1,u,v; i<n; ++i){cin>>u>>v; insert(u,v); insert(v,u);}string s; cin>>s; s=' '+s;for(int i=1; i<=n; ++i){if(s[i]=='1') has[i]=true;}
}
void dfs(int u, int father){for(int i=head[u];i;i=node[i].nxt){int v=node[i].to;if(v==father) continue;dfs(v,u); dp[u]+=dp[v];ans=max(ans,dp[v]+(has[u]));//最高点不炸,选择一棵子树}if(has[u]) dp[u]=max(dp[u]-1,1);ans=max(ans,dp[u]);//最高点可炸
}
int main(){ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);Read(); dfs(1,1); cout<<ans<<'\n';return 0;
}
若有不足请告诉我,谢谢啦。