Least_but_not_the_last's blog

By Least_but_not_the_last, history, 5 weeks ago, In English,

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.

 
 
 
 
  • Vote: I like it  
  • +10
  • Vote: I do not like it  

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I mean judging if first tree isomorphic to second tree if only "removing edge from first tree" allowed.

»
5 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

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.)

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

According to the faster time submission by gainullin.ildar there is a dynamic programming approach — edit distance with only Delete operation.