Cut 'em all! (Codeforces 982C)
Tags: Greedy, trees

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 \le n \le 10^5$$$) denoting the size of the tree. The next $$$n - 1$$$ lines contain two integers $$$u$$$, $$$v$$$ ($$$1 \le u, v \le 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.

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$$$.

Sample Inputs:
4
2 4
4 1
3 1

3
1 2
1 3

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

2
1 2

Sample Outputs:
1

-1

4

0

Solution (Python):
import threading
import sys
from sys import stdin
input = stdin.readline
sys.setrecursionlimit(10 ** 8)
from collections import defaultdict

def main():
    n = int(input())
    graph = [[] for _ in range(n)]
    for _ in range(n - 1):
        (a, b) = map(int, input().split())
        graph[a - 1].append(b - 1)
        graph[b - 1].append(a - 1)
    if n % 2:
        print(-1)
    else:
        ans = [0]

        def solve(root, node):
            temp = 1
            for nie in graph[root]:
                if nie != node:
                    temp += solve(nie, root)
            if temp % 2 == 0:
                ans[0] += 1
                return 0
            else:
                return temp
        solve(0, -1)
        print(ans[0] - 1)
threading.stack_size(10 ** 8)
t = threading.Thread(target=main)
t.start()
t.join()

Solution (Python):
import sys, threading
input = sys.stdin.readline

def solve(n, graph):
    stack = [0]
    parents = {}
    parents[0] = -1
    numNodes = [1] * n
    while stack:
        node = stack[-1]
        isleaf = True
        for nei in graph[node]:
            if nei not in parents:
                parents[nei] = node
                stack.append(nei)
                isleaf = False
        if isleaf:
            node = stack.pop()
            if node == 0:
                break
            numNodes[parents[node]] += numNodes[node]
    if numNodes[0] % 2 == 1:
        print(-1)
        exit()
    ans = -1
    for nums in numNodes:
        if nums % 2 == 0:
            ans += 1
    print(ans)
n = int(input())
graph = [[] for _ in range(n)]
for _ in range(n - 1):
    (u, v) = map(int, input().split())
    graph[u - 1].append(v - 1)
    graph[v - 1].append(u - 1)
solve(n, graph)

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
if n & 1 > 0:
    print(-1)
    exit()
g = [[] for i in range(n)]
for i in range(n - 1):
    (u, v) = map(int, input().split())
    u -= 1
    v -= 1
    g[u].append(v)
    g[v].append(u)
c = [1] * n
v = [-1] * n
v[0] = 0
q = [0]
while q:
    x = q[-1]
    flag = False
    for to in g[x]:
        if v[to] == -1:
            v[to] = x
            q.append(to)
            flag = True
    if not flag:
        q.pop()
        c[v[x]] += c[x]
ans = 0
for j in c[1:]:
    if j & 1 < 1:
        ans += 1
print(ans)