Codeforces Round #484 (Div. 2) C. Cut 'em all!(简单树形dp)

C. Cut 'em all!

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You're given a tree with nn 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 nn (1≤n≤1051≤n≤105) denoting the size of the tree.

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

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

Output

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

Examples

input

Copy

4
2 4
4 1
3 1

output

Copy

1

input

Copy

3
1 2
1 3

output

Copy

-1

input

Copy

10
7 1
8 4
8 10
4 7
6 5
9 3
3 5
2 10
2 5

output

Copy

4

input

Copy

2
1 2

output

Copy

0

Note

In the first example you can remove the edge between vertices 11 and 44. 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−1.

有一颗树，然后他想要删除一些边，使得每一块联通块中的点的个数是偶数，问你最多可以删除多少条边，不能的话就是-1

显然，如果点的个数为奇数的时候就是-1

然后首先dfs记录一下以i为根的子树的节点个数，接着再dfs一下，从底往上搜，如果出现num[i]为偶数的节点考虑删去，因为你是从下一点点遍历的，所以肯定会删除最少的2，除非出现一种情况，就是一颗小的子树，而非联通，这样可能就会要分开4个节点作为连通块（类似下图，这种结构不管你怎么分，都是不能再删除的），然后找到一次，记录ans++即可

#include <bits/stdc++.h>
#include <time.h>
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef double db;
int xx[4] = {1,-1,0,0};
int yy[4] = {0,0,1,-1};
const double eps = 1e-9;
typedef pair<int,int>  P;
const int maxn = 2e6 + 5000;
const ll mod = 1e9 + 7;
inline int sign(db a) { return a < -eps ? -1 : a > eps;}
inline int cmp(db a,db b){ return sign(a - b);}
ll mul(ll a,ll b,ll c) { ll res = 1; while(b) {  if(b & 1) res *= a,res %= c;  a *= a,a %= c,b >>= 1;  }  return res;}
ll phi(ll x) {  ll res = x;  for(ll i = 2; i * i <= x; i++) { if(x % i == 0) res = res / i * (i - 1);   while(x % i == 0) x /= i;   }  if(x > 1) res = res / x  * (x - 1);    return res;}
int fa[maxn];
int Find(int x) {   if(x != fa[x]) return fa[x] = Find(fa[x]);  return fa[x];}
ll c,n,k;
vector<int>v[maxn];
int cnt = 0;
int f[maxn];
int num[maxn];
void dfs(int x,int fa){
    for(auto d:v[x]){
        if(d == fa) continue;
        dfs(d,x);
        num[x] += num[d];
    }
    return ;
}
int ans = 0;
void dfs1(int x,int fa){
    for(auto d:v[x]){
        if(d == fa) continue;
        if(num[d] % 2 == 0) ans++;
        dfs1(d,x);
    }
    return ;
}
int main() {
    ios::sync_with_stdio(false);
    while(cin >> n){
         for(int i = 1;i < n;i++){
            int u,vv;
            cin >> u >> vv;
            v[u].push_back(vv);
            v[vv].push_back(u);
         }
         if(n & 1){
            cout << -1 << endl;
            continue;
         }
         for(int i = 1;i <= n;i++) num[i] = 1;
         dfs(1,0);
//         for(int i = 1;i <= n;i++){
//            cout << num[i] << endl;
//         }
         dfs1(1,0);
         cout << ans << endl;
    }
    cerr << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
    return 0;
}