题目链接：https://codeforces.com/problemset/problem/1689/C
题意：给定一棵树，除根节点的度数最多为2，其他节点的度数最多为3。有一个病毒从根节点开始向下蔓延，每次病毒会向其下一层的所有子节点蔓延，同时每次我们可以选择删除一个节点，那么以该节点为根的所有子节点就被救下来不会被感染了（不包括删去的节点）。问最多能救下来多少节点。
思路：简单的树形DP，我们可以用
D
P
[
u
]
DP[u]
DP[u]表示以点u被感染，能救下来的子节点的个数。因为除根节点外的其他节点的度数最多为3，那么每个节点最多有2个子节点，对于每个节点我们每次会选取其中一个子节点删除，用
s
z
[
u
]
sz[u]
sz[u]表示以点u为根的子节点的个数，
s
1
,
s
2
s1,s2
s1,s2表示点u的两个子节点，那么删除
s
1
s1
s1的答案就是
s
z
[
s
1
]
?
1
+
d
p
[
s
2
]
sz[s1]-1+dp[s2]
sz[s1]?1+dp[s2]，如果删除
s
2
s2
s2，那么答案就是
s
z
[
s
2
]
?
1
+
d
p
[
s
1
]
sz[s2]-1+dp[s1]
sz[s2]?1+dp[s1]，还要特判一下对于每个节点只有一个儿子和没有儿子的情况，具体看代码：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 1e5 + 10,INF=1e9;
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int T;cin>>T;
while(T--)
{
int n;cin>>n;
vector<vector<int>>g(n+1);
for(int i=0;i<n-1;i++)
{
int u,v;cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
vector<int>sz(n+1,0),dp(n+1,0);
auto dfs = [&](auto&& dfs,int u,int fa)->int
{
sz[u]=1;
int s1=-1,s2=-1;//表示点u的两个子节点
for(auto j:g[u])
{
if(j==fa)continue;
dfs(dfs,j,u);
sz[u]+=sz[j];//统计以点u为根节点的子节点个数
if(s1==-1)s1=j;
else if(s2==-1)s2=j;
}
if(s1==-1)return dp[u]=0;//特判没有子节点的情况
if(s2==-1)return dp[u]=sz[s1]-1;//特判只有一个子节点的情况
return dp[u]=max(sz[s1]-1+dp[s2],sz[s2]-1+dp[s1]);//有两个子节点的情况
};
cout<<dfs(dfs,1,-1)<<"
";;
}
return 0;
}