E69 树形DP P2899 USACO08JAN Cell Phone Network G

// 树形DP O(n)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=20005;
int idx,head[N],to[N],ne[N];
void add(int u,int v){
  to[++idx]=v;ne[idx]=head[u];head[u]=idx;
}
int n,f[N][3]; //0自己/1儿子/2父亲

void dfs(int u,int fa){
  int t=0;f[u][0]=1;
  for(int i=head[u];i;i=ne[i]){
    int v=to[i];
    if(v==fa) continue;
    dfs(v,u);
    f[u][0]+=min(f[v][0],min(f[v][1],f[v][2]));
    f[u][2]+=min(f[v][0],f[v][1]);
    if((f[t][0]-min(f[t][0],f[t][1]))
      >(f[v][0]-min(f[v][0],f[v][1]))) t=v;
  }
  f[u][1]=f[t][0]; //t为最优儿子
  for(int i=head[u];i;i=ne[i]){
    int v=to[i];
    if(v==fa||v==t) continue;
    f[u][1]+=min(f[v][0],f[v][1]);
  }
}
int main(){
  scanf("%d",&n);
  for(int i=1,u,v;i<n;i++)
    scanf("%d%d",&u,&v),add(u,v),add(v,u);
  f[0][0]=2e9;
  dfs(1,0);
  printf("%d",min(f[1][0],f[1][1]));
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10, inf=0x3f3f3f3f;
vector<int> G[N];
int f[N][4];
void dfs(int x, int fa){
    f[x][1]=1;
    int t=inf; bool flag=0;
    for(int y: G[x]) if(y!=fa){
        dfs(y, x); 
        flag=1;
        t=min(t, f[y][1]-f[y][0]);
        f[x][0]+=min(f[y][1], f[y][0]);
        f[x][1]+=min({f[y][0], f[y][1], f[y][2]});
        f[x][2]+=min(f[y][0], f[y][1]);
        
    }
    if(t>0) f[x][0]+=t;
    //当是叶子节点的时候，f[x][0]要为正无穷 
}
int main(){
    int n; scanf("%d", &n);
    for(int i=1; i<n; i++){
        int x, y; scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    memset(f, 0, sizeof(f));
    dfs(1, 0);
    printf("%d\n", min(f[1][0], f[1][1]));
    return 0;
}