i 表示节点 i ，j=0表示不选择其父节点，j=1表示选择其父节点。f 为其父节点。

取 每个节点选择/不选择 两者中较小的那个。

一组数据：

15

1 2

1 3

1 4

1 10

10 9

10 11

12 10

12 14

10 13

13 15

4 5

5 7

4 6

6 8

答案是6

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #include 
         
           6  7 using namespace std; 8  9 const int MAXN = 100010;10 11 vector
          
            adj[MAXN];12 bool vis[MAXN][2];13 int d[MAXN][2];14 int n, m;15 //int path[MAXN][2];16 //int fang[MAXN];17 18 int dp( int i, int j, int f )19 {20 if ( vis[i][j] ) return d[i][j];21 vis[i][j] = true;22 int &ans = d[i][j];23 24 ans = 1;25 for ( int k = 0; k < (int)adj[i].size(); ++k )26 if ( adj[i][k] != f ) ans += dp( adj[i][k], 1, i );27 //path[i][j] = f;28 29 if ( j || f < 0 )30 {31 int sum = 0;32 for ( int k = 0; k < (int)adj[i].size(); ++k )33 if ( adj[i][k] != f )34 sum += dp( adj[i][k], 0, i );35 if ( sum < ans )36 {37 ans = sum;38 //path[i][j] = -f;39 }40 }41 return ans;42 }43 44 //void DFS( int i, int j, int f )45 //{46 // if ( fang[i] != -1 ) return;47 // if ( !path[i][j] || path[i][j] == f )48 // {49 // if ( f >= 0 ) fang[f] = j;50 // for ( int k = 0; k < (int)adj[i].size(); ++k )51 // if ( adj[i][k] != f ) DFS( adj[i][k], 1, i );52 // }53 // else54 // {55 // if ( f >= 0 ) fang[f] = j;56 // for ( int k = 0; k < (int)adj[i].size(); ++k )57 // if ( adj[i][k] != f ) DFS( adj[i][k], 0, i );58 //59 // }60 // return;61 //}62 63 int main()64 {65 while ( ~scanf( "%d", &n ) )66 {67 m = n - 1;68 for ( int i = 0; i <= n; ++i ) adj[i].clear();69 70 for ( int i = 0; i < m; ++i )71 {72 int a, b;73 scanf( "%d%d", &a, &b );74 adj[a].push_back(b);75 adj[b].push_back(a);76 }77 78 memset( vis, false, sizeof(vis) );79 //memset( fang, -1, sizeof(fang) );80 //memset( path, 0, sizeof(path) );81 82 int ans = dp( 1, 0, -1 );83 printf( "%d\n", ans );84 }85 return 0;86 }