I don't know whether this idea has been discussed somewhere before, but I find it quite interesting.
Summary of the problem: Given a tree find a largest set of edges such that no two edges share an endpoint (maximum matching), or to find minimal set of nodes such that each node outside the set must be adjacent to at least one node in the set (minimum vertex cover).
Usual algorithm: Dynamic programming (refer to this blog : Codeforces blog)
My (maybe-wrong) greedy idea:
Root the tree at arbitrary node, let say node 1.
Find the distances of other nodes to node 1 (means find the height of each node). Sort the nodes according to their distances to node 1 (means sort by height).
Go from the node with greatest height, if this node is not used and its parent is not used, then we match this node with its parent.
My correct submission to above SPOJ problem: https://ideone.com/CeWhlr
Could anyone prove or disprove it? Thanks in advanced!
