Can someone please explain how to solve this problem https://www.hackerearth.com/march-clash-15/algorithm/counting-on-tree-1/description/ using centroid tree decomposition.

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

1 | tourist | 3771 |

2 | jiangly | 3688 |

3 | Um_nik | 3539 |

4 | slime | 3498 |

5 | djq_cpp | 3486 |

6 | MiracleFaFa | 3466 |

7 | ksun48 | 3452 |

8 | Radewoosh | 3406 |

9 | greenheadstrange | 3393 |

10 | xtqqwq | 3382 |

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

1 | -is-this-fft- | 183 |

2 | awoo | 181 |

3 | YouKn0wWho | 177 |

4 | Um_nik | 175 |

5 | dario2994 | 172 |

6 | Monogon | 171 |

7 | adamant | 168 |

8 | maroonrk | 167 |

9 | antontrygubO_o | 166 |

10 | errorgorn | 164 |

Can someone please explain how to solve this problem https://www.hackerearth.com/march-clash-15/algorithm/counting-on-tree-1/description/ using centroid tree decomposition.

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/09/2022 05:39:45 (j3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

I really liked the problem and after a bit thinking I think I found a solution with centroid decomposition. The main idea is that each time after we pick a new centroid with dynamic programming we look at the number of

beautifulsubsets with our centroidincludedin them.First idea which comes to our mind is to root the current subgraph at the centroid and then do dynamic programming with state dp[u][k'] = number of subsets with root u and sum of values k'. The most basic way is to make for every state

O(K) transitions so overall complexity of the dp will beO(NK^{2}). And then complexity of the solution will be .By the way this dp is actually a valid solution to the problem. We can simply pick an arbitrary vertex of our tree as a root and do the dp. Then the answer will be . And the complexity will be

O(NK^{2}).Lets go back to our centroid decomposition solution. To make it more efficient. We will change the dynamic programming to dp[i][k'] = number of subsets on the first i vertices with root equal to our centroid with sum of values k'. By "first i" I mean first i in dfs order. It's not hard to do this in

O(NK) time. So in such a way we create an solution.