> File Name: 5753.cpp > Author: jiangyuzhu > Mail: 834138558@qq.com > Created Time: 2016/9/27 21:27:27 ************************************************************************/ #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<set> #include<map> #include<algorithm> using namespace std; const int maxn = 1e5 + 5, oo = 0x3f3f3f3f; struct EDGE{ int to, next; }edge[maxn * 2 + 5]; int head[maxn]; int tot = 0; void addedge(int u, int v) { edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++; } int out[maxn]; int leaf; int son[maxn]; int times[maxn * 2 + 5]; int ans; void init() { tot = 0; leaf = 0; ans = 0; memset(head, -1, sizeof(head)); memset(out, 0, sizeof(out)); memset(son, 0, sizeof(son)); memset(times, 0, sizeof(times)); } int dfs(int u, int pa) { int tmp; for(int i = head[u]; i != -1; i = edge[i].next){ int v = edge[i].to; if(v == pa) continue; dfs(v, u); son[u] += son[v]; if(son[v] & 1) times[i] = times[i ^ 1] = 1; else times[i] = times[i ^ 1] = 2; ans += times[i]; } if(son[u] == 0) leaf++, son[u] = 1; } int TMP, tmp; void dfs2(int u, int pa, int now) { TMP = max(TMP, now); for(int i = head[u]; i != -1; i = edge[i].next){ int v = edge[i].to; if(v == pa) continue; if(times[i] == 1) tmp = -1; else tmp = 1; dfs2(v, u, now + tmp); } } int main (void) { int T;scanf("%d", &T); while(T--){ int n;scanf("%d", &n); int x, y; init(); for(int i = 0; i < n - 1; i++){ scanf("%d%d", &x, &y); addedge(x, y);addedge(y, x); out[x]++; out[y]++; } dfs(1, 1); if(out[1] == 1) leaf++; if(leaf & 1){ TMP = 0; dfs2(1, 1, 0); printf("%d\n", ans - TMP); }else printf("%d\n", ans); } return 0; }
| 