CF 982C

C. Cut 'em all!

time limit per test1 second

memory limit per test256 megabytes

inputstandard input

outputstandard output

You’re given a tree with n vertices.

Your task is to determine the maximum possible number of edges that can be removed in such a way that all the remaining connected components will have even size.

Input

The first line contains an integer n (1≤n≤105) denoting the size of the tree.

The next n−1 lines contain two integers u, v (1≤u,v≤n) each, describing the vertices connected by the i-th edge.

It’s guaranteed that the given edges form a tree.

Output

Output a single integer k — the maximum number of edges that can be removed to leave all connected components with even size, or −1 if it is impossible to remove edges in order to satisfy this property.

Examples

inputCopy

4

2 4

4 1

3 1

outputCopy

1

inputCopy

3

1 2

1 3

outputCopy

-1

inputCopy

10

7 1

8 4

8 10

4 7

6 5

9 3

3 5

2 10

2 5

outputCopy

4

inputCopy

2

1 2

outputCopy

0

Note

In the first example you can remove the edge between vertices 1 and 4. The graph after that will have two connected components with two vertices in each.

In the second example you can’t remove edges in such a way that all components have even number of vertices, so the answer is −1.

题意：给你一棵树，即n个节点n-1条边，问最多能删除多少边，使得各个子树的节点数为偶数。

一开始想当然的以为，奇数个节点直接输出-1，偶数个节点答案即为节点数/2 - 1，多画了几个图才发现不对。

dfs遍历，如果当前节点的子树个数（包括该节点自身）为偶数，则答案ans++。因为偶数+偶数 = 偶数，巧妙

#include <bits/stdc++.h> 
using namespace std;
const int maxn = 1e5 + 10;
int n;
vector<int> g[maxn];
int ans;
int dfs(int x, int fa){
    int sum = 1;
    int sz = g[x].size();
    for(int i = 0; i < sz; i++)
    {
        int t = g[x][i];
        if(t != fa)
        {
            sum += dfs(t, x);
        }
    }
    if(sum % 2 == 0)    ans++;
    return sum;
}
int main()
{
    cin >> n;
    int a, b;
    for(int i = 0; i < n - 1; i++){
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    if(n & 1){
        cout << "-1" << endl;
        return 0;
    }
    dfs(1, 0);
    cout << ans - 1 << endl; //减去最后的自己 
    return 0;
}