2016多校训练3_1007(hdu5758 Explorer Bo)

  1 #include <functional>
  2 #include <algorithm>
  3 #include <iostream>
  4 #include <iterator>
  5 #include <sstream>
  6 #include <fstream>
  7 #include <numeric>
  8 #include <iomanip>
  9 #include <climits>
 10 #include <utility>
 11 #include <complex>
 12 #include <cstdlib>
 13 #include <cstring>
 14 #include <cassert>
 15 #include <string>
 16 #include <vector>
 17 #include <cctype>
 18 #include <bitset>
 19 #include <cstdio>
 20 #include <cmath>
 21 #include <ctime>
 22 #include <deque>
 23 #include <stack>
 24 #include <queue>
 25 #include <deque>
 26 #include <list>
 27 #include <new>
 28 #include <map>
 29 #include <set>
 30 using namespace std;
 31 
 32 typedef long long LL;
 33 typedef pair<int, int> PII;
 34 typedef pair<PII, int> PIII;
 35 #define PB push_back
 36 #define FI first
 37 #define SE second
 38 #define gcd(x, y) __gcd(x, y)
 39 #define gcd3(x, y, z) __gcd(__gcd(x, y), z)
 40 
 41 const double EPS = 1e-8;
 42 const double PI = acos(-1.0);
 43 const int INF = 0x3f3f3f3f;
 44 const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
 45 const int MAXN = 100000 + 10;
 46 const int MOD = 1e9 + 7;
 47 
 48 int n;
 49 vector<int> G[MAXN];
 50 int dp[MAXN][2], deg[MAXN], lf[MAXN];
 51 
 52 void dfs(int u, int fa) {
 53     dp[u][0] = lf[u] = 0;
 54     for (int i = 0, sz = G[u].size(); i < sz; ++i) {
 55         int v = G[u][i];
 56         if (v == fa) continue;
 57         dfs(v, u);
 58         lf[u] += lf[v];
 59         int d = (lf[v] & 1) ? 1 : 2;
 60         dp[u][0] += dp[v][0] + d;
 61     }
 62     dp[u][1] = INF;
 63     for (int i = 0, sz = G[u].size(); i < sz; ++i) {
 64         int v = G[u][i];
 65         if (v == fa) continue;
 66         if (lf[v] == 1) dp[u][1] = min(dp[u][1], dp[u][0]);
 67         int d = (lf[v] & 1) ? 1 : -1;
 68         dp[u][1] = min(dp[u][1], dp[u][0] - dp[v][0] + dp[v][1] + d);
 69     }
 70     if (G[u].size() == 1) lf[u] = 1;
 71 }
 72 
 73 
 74 int main() {
 75     int T;
 76     cin >> T;
 77     while (T--) {
 78         scanf("%d", &n);
 79         for (int i = 0; i < MAXN; ++i) {
 80             G[i].clear();
 81         }
 82         memset(dp, 0, sizeof(dp));
 83         memset(deg, 0, sizeof(deg));
 84         memset(lf, 0, sizeof(lf));
 85         for (int i = 0; i < n - 1; ++i) {
 86             int u, v;
 87             scanf("%d%d", &u, &v);
 88             G[u].PB(v);
 89             G[v].PB(u);
 90             deg[u]++;
 91             deg[v]++;
 92         }
 93         if (n == 2) {
 94             puts("1");
 95             continue;
 96         }
 97         int leaf = 0, rt;
 98         for (int i = 1; i <= n; ++i) {
 99             if (deg[i] == 1) {
100                 leaf++;
101             } else {
102                 rt = i;
103             }
104         }
105         dfs(rt, -1);
106         printf("%d
", dp[rt][leaf & 1]);
107     }
108     return 0;
109 }