Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

### Least_but_not_the_last's blog

By Least_but_not_the_last, history, 9 months ago, ,

This is the problem. Here we can't change child order. But how you would solve this problem if we could change child order? Thanks.

•
• +10
•

 » 9 months ago, # |   0 I mean judging if first tree isomorphic to second tree if only "removing edge from first tree" allowed.
 » 9 months ago, # |   +20 There is still a polynomial solution. No idea whether this is close to being optimal, it probably isn't, it's just the first thing that came to my mind.We will have a memoized recursive function match(u,v) that returns whether the subtree of tree 1 rooted at u can be changed into the subtree of tree 2 rooted at v. Clearly, match(root1,root2) is what we want.Here is what match(u,v) does: Let u1,...,ux be the children of u, and let v1,...,vy be the children of v. Make a bipartite graph where the ui are one partition, the vj are the other, and edges correspond to match(ui,vj) being true. Then, match(u,v) returns true iff this bipartite graph has a matching of size y. (The matching also tells you which subtree of u should be pruned to produce which subtree of v.)
•  » » 9 months ago, # ^ |   0 Then total complexity should be?
•  » » 9 months ago, # ^ |   +5 Yes. Bipartite matching should work here. Thanks misof. Any other smart thinking is appreciable.
 » 8 months ago, # |   0 According to the faster time submission by gainullin.ildar there is a dynamic programming approach — edit distance with only Delete operation.
•  » » 8 months ago, # ^ |   0 Can you explain a bit more?
•  » » 8 months ago, # ^ |   +5 I think it's when they can change the child order, right? We're discussing about when we can't change the child order.
•  » » » 8 months ago, # ^ |   +5 yes.