```cpp
#include<bits/stdc++.h>
#define int long long
#define mem(x,y) memset(x,y,sizeof(x))
#define frein freopen("in.in","r",stdin)
#define freout freopen("out.out","w",stdout)
using namespace std;
int read(){
int s = 0,w = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
return s * w;
}
struct node{
int to;
int nxt;
}e[3000010];
int cnt,head[3000010];
int n;
int dp[3000010][4];//自己染自己是2，父亲染自己是3，儿子染自己是1
void add(int x,int y){
cnt ++;
e[cnt].to = y;
e[cnt].nxt = head[x];
head[x] = cnt;
}
void dfs(int x,int fa){
vector <int> q;
for(int i = head[x];i;i = e[i].nxt){
int v = e[i].to;
if(v != fa){
dfs(v,x);
dp[x][2] += min(dp[v][3],min(dp[v][1],dp[v][2]));
dp[x][3] += min(dp[v][1],dp[v][2]);
dp[x][1] += dp[v][2];
q.push_back(dp[v][1] - dp[v][2]);
}
}
if(!q.size())dp[x][1] = 2147483647777;
else {
sort(q.begin(),q.end());
for(int i = 0;i <= q.size() - 2;i ++){
if(q[i] < 0)dp[x][1] += q[i];
else break;
}
}
}
signed main(){
cin>>n;
for(int i = 1;i <= n - 1;i ++){
int x,y;
x = read(),y = read();
add(x,y);
add(y,x);
}
for(int i = 1;i <= n;i ++)dp[i][2] = 1;
dfs(1,-1);
cout<<min(dp[1][1],dp[1][2]);
}
```
by EDqwq @ 2021-07-10 00:16:52
@[EDqwq](/user/294562)
100
```cpp
#include<bits/stdc++.h>
#define int long long
#define mem(x,y) memset(x,y,sizeof(x))
#define frein freopen("in.in","r",stdin)
#define freout freopen("out.out","w",stdout)
using namespace std;
int read(){
int s = 0,w = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
while(ch >= '0' && ch <= '9')s = s * 10 + ch - '0',ch = getchar();
return s * w;
}
struct node{
int to;
int nxt;
}e[3000010];
int cnt,head[3000010];
int n;
int dp[3000010][4];
void add(int x,int y){
cnt ++;
e[cnt].to = y;
e[cnt].nxt = head[x];
head[x] = cnt;
}
void dfs(int x,int fa){
vector <int> q;
for(int i = head[x];i;i = e[i].nxt){
int v = e[i].to;
if(v != fa){
dfs(v,x);
dp[x][2] += min(dp[v][3],min(dp[v][1],dp[v][2]));
dp[x][3] += min(dp[v][1],dp[v][2]);
dp[x][1] += dp[v][2];
q.push_back(dp[v][1] - dp[v][2]);
}
}
if(!q.size())dp[x][1] = 2147483647777;
else {
sort(q.begin(),q.end());
int end=q.size()-2; //新增
for(int i = 0;i <= end;i ++){
if(q[i] < 0)dp[x][1] += q[i];
else break;
}
}
}
signed main(){
cin>>n;
for(int i = 1;i <= n - 1;i ++){
int x,y;
x = read(),y = read();
add(x,y);
add(y,x);
}
for(int i = 1;i <= n;i ++)dp[i][2] = 1;
dfs(1,-1);
cout<<min(dp[1][1],dp[1][2]);
}
```
by 天南星魔芋 @ 2021-07-10 07:38:10
@[天南星魔芋](/user/399239) 能告知一下为什么吗 看上去并没有差异
by EDqwq @ 2021-07-10 12:44:41
@[EDqwq](/user/294562) 用 `//` 标注释了啊
`sort` 附近
by 天南星魔芋 @ 2021-07-10 12:58:13