is it possible to find biparite matching for n or n logn? if we divide graph into 2 parts - maximal matching is the answer. But biparite matching founding time is NM(max-flow) so N*N(because it's tree).
AFAIK, Fastest biparite matching algorithm - Hopcroft Carp, with complexity E*sqrt(V); V-num of vertices; E - num of edges; Given graph is a tree, so it's possible to color it into 2 colors, after that, take all black vertices as one part, white as other part and find max matching between them. I can't give strict evidence of this approach but it intuitively understandable - just draw sample output on the paper and everything will become clear=) You can see my code -> i shared my account here http://acm.timus.ru/forum/thread.aspx?id=25749&upd=634266195834002500 Just look my submission.