even-tree.py

#!/usr/bin/python
# -*- coding: utf-8 -*-

import sys
from treelib import Node, Tree

ROOT = 1


# Read the tree
tree = Tree()
tree.create_node(ROOT, ROOT, data=1)  # data means weight

n, m = 0, 0
for line in sys.stdin:
    u, v = [int(x) for x in line.split()]
    if n == 0:  # Process the first line
        n, m = u, v
    else:
        if tree.contains(int(u)):
            tree.create_node(v, v, parent=u, data=1)
        elif tree.contains(int(v)):
            tree.create_node(u, u, parent=v, data=1)


# Process the tree
edges_removed = 0

while tree.depth() > 0:
    for leaf in tree.leaves(ROOT):
        leaf_id = leaf.identifier

        parent = tree.parent(leaf_id)

        # If the total weigth is even, we can cut this edge
        if leaf.data % 2 == 0:
            edges_removed += 1

        # Glue the leaves to their parents, making them heavier
        # (Cutting does not affect the parity)
        parent.data += leaf.data
        tree.remove_node(leaf_id)


# Output the result
print edges_removed