```cpp
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
const int N=5e5+5;
#define For(i,l,r) for(register int i=l;i<=r;i++)
#define int __int128
inline void read(int &x){
x=0;int f=1;
char c=getchar();
while(!isdigit(c)){
if(c=='-') f=-1;
c=getchar();
}while(isdigit(c)){
x=x*10+c-'0';
c=getchar();
}x*=f;
}
inline void write(int x){
if(x<0){x=-x;putchar('-');}
if(x>9) write(x/10);
putchar(x%10+'0');
}int n,x,y;
vector<int> edge[N];
int f[N][3];
/*
f[u][0]被himself覆盖 f[u][0]+=min{f[v][1],f[v][0],f[v][2]}
f[u][1]被son覆盖 f[u][1]=f[x][0]+sigma{min{f[v][0],f[v][1]}}
f[u][2]被fa覆盖 f[u][2]+=min{f[v][0],f[v][1]}
*/
inline void dfs(int u,int fa){
f[u][0]=1;f[u][1]=1e18;
int Min0=1e18,sum=0,id=0;
for(int j=0;j<edge[u].size();j++){
int v=edge[u][j];
if(v!=fa){
dfs(v,u);
f[u][0]+=min(min(f[v][0],f[v][1]),f[v][2]);
if((f[id][0]-min(f[id][0],f[id][1])) > (f[v][0]-min(f[v][0],f[v][1])))
id=v;
f[u][2]+=min(f[v][0],f[v][1]);
}
}for(int j=0;j<edge[u].size();j++){
int v=edge[u][j];
if(v!=fa&&v!=id){
sum+=min(f[v][0],f[v][1]);
}
}f[u][1]=f[id][0]+sum;
}
signed main(){
read(n);
for(int i=1;i<=n-1;i++){
read(x);read(y);
edge[x].push_back(y);
edge[y].push_back(x);
}
f[0][0]=1e8;
dfs(1,-1);
write(min(f[1][0],f[1][1]));
return 0;
}
```
1.转移方程有问题
2.求答案（为什么有入度？树形dp啊！！）
by allen2010 @ 2023-09-27 21:44:35