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 <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <algorithm> 5 #include <vector> 6 7 using namespace std; 8 9 const int MAXN = 100010; 10 11 vector<int> 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 // else 54 // { 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 ", ans ); 84 } 85 return 0; 86 }