Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### ghost016's blog

By ghost016, 9 years ago, ,
Hello all,

Recently i am stuck with a problem, which i was trying on my own for couple of days, i have two different trees which are weighted, weights are assigned in some basis which are not of the concern now, anywayz i thought of transforming it into bipartite graph and then find the maximum weighted matching between them, but next i thought of doing the maximum tree matching rather then transforming into graph and then doing the match, now i am stuck here, i really want to know how to do it. Many good coders are here, please any one help me with this.

ThankS
Ghost016

• +11

 9 years ago, # |   +16 As far as I understand, your problem is: "You have a weighted tree, you need to find maximal matching".You can do simple DP.dp1[v] - The maximal matching of the subtree rooted by v where v is already covered by matching.dp2[v] - The maximal matching of the subtree rooted by v where v isn't covered by matching yet.
•  9 years ago, # ^ |   0 Hello, Thankz for your reply, however i asked for the maximum matching, not maximal matching, but thanks anywayz for the reply, and one more thing, can you please tell me an algorithm for these i.e for maximum matching which is btw faster then hungarian. And i am really bad at DP, i think this wont work with me, but i can see u formulated it nicely. Do you have a source code for this ???ThanksGhost016
•  9 years ago, # ^ |   0 Actually the algorithm described above finds exactly what you need, i.e. maximum matching.
•  9 years ago, # ^ |   0 All right then. Well in that case can you please tell me what is the run-time of this algorithm ??ThanksGhost016
•  9 years ago, # ^ |   0 If it is implemented optimally, then the complexity is O(N).
•  9 years ago, # ^ |   0 And i thought the best you could do is E*SQRT(V) using hopcroft!
•  9 years ago, # ^ |   0 The problem is to find matching in tree, so we can use dynamic programming. Hopcroft-Karp algorithm is for cyclic bipartite graphs, although it can't find weighted matching. To find maximal matching in tree is quite easier than in cyclic graph.
•  9 years ago, # ^ |   0 This may be stupid question but, how this works if the tree is unrooted .. i mean no parent child relation defined .. would rooting it at any random vertex and running this dp gives the maximum matching in every case ?
•  9 years ago, # ^ |   0 Hmm infact it does ..tested it here https://www.spoj.pl/problems/PT07X/thanks
 9 years ago, # |   0 Hi..This thing is really new for me and the theory really look nice .... can anyone please give me source code for this .... i am really interested to learn this ... Thank YouGhost016
 » 21 month(s) ago, # |   0 Are there any problems in the Online Judges about Maximum Matching on the tree?I cannot find (only there is minimum Vertex Cover on the tree).I want to give it for my school students
•  » » 21 month(s) ago, # ^ |   +6 In bipartite Graphs ( like trees ) maximum matching = vertex cover !
•  » » 21 month(s) ago, # ^ | ← Rev. 2 →   0 Hmmmmm. Mb it's http://acm.timus.ru/problem.aspx?space=1&num=1109 ?