Least_but_not_the_last's blog

SRM 731 Div1_easy
By Least_but_not_the_last, history, 7 years 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

Comments Comments (5)
| Write comment?
»
7 years 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.)

→ Reply
»
7 years 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.

→ Reply