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

1 | tourist | 3624 |

2 | Um_nik | 3468 |

3 | mnbvmar | 3363 |

4 | Petr | 3330 |

5 | wxhtxdy | 3329 |

6 | LHiC | 3300 |

7 | sunset | 3278 |

8 | V--o_o--V | 3275 |

9 | Vn_nV | 3182 |

10 | dotorya | 3156 |

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

1 | Radewoosh | 190 |

2 | Errichto | 185 |

3 | rng_58 | 161 |

3 | PikMike | 161 |

5 | Petr | 156 |

6 | Ashishgup | 153 |

6 | Vovuh | 153 |

8 | neal | 151 |

8 | majk | 151 |

8 | 300iq | 151 |

8 | Um_nik | 151 |

↑

↓

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/26/2019 22:36:58 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Direct the edge from node

vtoL_{v}and fromR_{v}tov.Now the problem becomes "How many ways are there to arrange the vertices such that the arrangement is topologically sorted."

Let

dp_{}(v,i) be how many topological sorts with the vertices fromv's subtree are there such that there are exactlyivertices behind the vertexv.Now updating the dp is easy.

I didn't understand your approach very clearly ... I have understood how you have reduced the problem to number of ways to order the vertices that are topologically sorted. But I didn't get what your dp state represents. Can you explain your dp state more clearly and the recurrence ?

This is the solution for any tree and not just binary trees.

Wow, thanks!