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.

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

# | User | Rating |
---|---|---|

1 | tourist | 3469 |

2 | Radewoosh | 3357 |

3 | OO0OOO00O0OOO0O0…O | 3264 |

4 | LHiC | 3227 |

5 | ksun48 | 3184 |

6 | scott_wu | 3168 |

7 | Um_nik | 3166 |

8 | CongLingDanPaiSh…5 | 3157 |

9 | Petr | 3139 |

10 | V--o_o--V | 3135 |

# | User | Contrib. |
---|---|---|

1 | Radewoosh | 195 |

2 | Errichto | 175 |

3 | rng_58 | 158 |

4 | Ashishgup | 157 |

4 | neal | 157 |

6 | tourist | 154 |

7 | PikMike | 152 |

8 | Petr | 151 |

9 | Um_nik | 149 |

10 | kostka | 148 |

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.

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/19/2018 11:48:25 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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

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

Then total complexity should be?

Yes. Bipartite matching should work here. Thanks misof. Any other smart thinking is appreciable.

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

Can you explain a bit more?

I think it's when they can change the child order, right? We're discussing about when we can't change the child order.

yes.