CF1689C Infected Tree 题解
怎么只有我这个蒟蒻不会 DP 啊。
回归正题……
简化题意
给定一棵以 $1$ 号节点为根的二叉树，总节点个数为 $n$。现在 $1$ 号节点感染了病毒，你在这一回合里可以使病毒所在节点的一个儿子不被感染，而病毒会感染一个不受保护的儿子。
询问最多可以有多少不被病毒感染且不被保护的点。
思路整理
这是二叉树!!!
由于我们要求最多不被感染且不被保护的点，可以贪心地想：想要答案最大，不就是病毒行走路径最短吗？
DP 来干嘛？DFS 就完事了嘛!
设置变量 $ans$，表示被保护的点和被感染的点的总和；设当前节点儿子数量为 $D$。
如果 $D = 0$，说明病毒已经无法继续感染了，那么 $ans = \max(ans, now)$。
如果 $D = 1$，说明只要保护子节点，病毒将无法继续感染了，那么 $ans = \max(ans, now)$。
如果 $D = 2$，说明防疫工作仍然漫长，那么继续向下搜索。
最终答案就是 $n - ans$。
核心代码：
void dfs(int fa, int root, int now){
if(G[root].size() == 1){
if(now < ans)ans = now;//病毒感染到树顶
return ;
}
if(G[root].size() == 2){
if(now + 1 < ans)ans = now + 1//只有一个儿子, 赶紧保护;
return ;
}
for(int i = 0; i < G[root].size(); i++){
if(G[root][i] == fa)continue;
dfs(root, G[root][i], now + 2); // now + 2是因为你要保护一个儿子，而病毒会感染一个孩子
}
}
代码运行很成功，没有花里胡哨的优化，但是当时是最优解。