Hrbust 2310 Tree Painting（欧拉路径性质）

Tree Painting Time Limit: 1000 MSMemory Limit: 131072 K Total Submit: 42(22 users)Total Accepted: 19(16 users)Rating: Special Judge: No Description Give you a tree, can you draw the tree with minimum strokes without overlapping? Noted that it is ok if two strokes intersect at one point. Here we define a tree as a connected undirected graph with N points and N-1 edges. Input

The input data has several test cases. The first line contains a positive integer T (T<=20), indicates the number of test cases.

For each case:

The first line contains an integers N (2<=N<=10^5), indicates the number of points on the tree numbered from 1 to N.

Then follows N-1 lines, each line contains two integers Xi, Yi means an edge connected Xi and Yi (1<=Xi, Yi<=N).

Output For each test case, you should output one line with a number K means the minimum strokes to draw the tree. Sample Input

2

2

1 2

5

1 2

1 5

2 3

2 4

Sample Output

1

2

Source "尚学堂杯"哈尔滨理工大学第六届程序设计竞赛

题意：给出一颗N个点N-1条边的树，问至少能有几笔画出来

欧拉路径性质：每有两个度数为级数的顶点就存在一条欧拉路径

#include <bits/stdc++.h> using namespace std; int t, n; int a[100000 + 10]; int main(){ scanf("%d", &t); while(t--){ scanf("%d", &n); memset(a, 0, sizeof(a)); for(int i = 1; i < n; i++){ int x, y; scanf("%d%d", &x, &y); a[x]++, a[y]++; } int ans = 0; for(int i = 1; i <= n; i++){ if(a[i]&1) ans++; } printf("%d\n", ans>>1); } }