I have recently learnt the rerooting technique from the previous contest. I will be greatful if someone will please share some problems related to it.

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

1 | tourist | 3882 |

2 | maroonrk | 3539 |

3 | Benq | 3513 |

4 | MiracleFaFa | 3466 |

5 | ksun48 | 3462 |

6 | ecnerwala | 3446 |

7 | slime | 3428 |

8 | Um_nik | 3426 |

9 | jiangly | 3401 |

10 | greenheadstrange | 3393 |

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

1 | awoo | 192 |

2 | -is-this-fft- | 191 |

3 | Monogon | 184 |

4 | YouKn0wWho | 182 |

4 | Um_nik | 182 |

6 | antontrygubO_o | 170 |

7 | maroonrk | 169 |

8 | kostka | 165 |

9 | SecondThread | 164 |

9 | errorgorn | 164 |

I have recently learnt the rerooting technique from the previous contest. I will be greatful if someone will please share some problems related to it.

↑

↓

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/23/2022 23:34:14 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Codeforces Round #527 (Div. 3) Problem F

thanks

https://codeforces.com/contest/1324/problem/F

Well done, would you join our Clan!

ok (clan like some group for practicing algos and problems i assume).

https://www.hackerearth.com/practice/algorithms/graphs/depth-first-search/practice-problems/algorithm/parwal-problem/

1187E - Tree Painting One of the best problem on rerooting!!

This comment have few more nice problems on rerooting.

This one was fun to work out: https://codeforces.com/contest/960/problem/E

this one: Atcoder dp_v

if we use rerooting in this problem, won't we have to use modular inverse at some point, and it is not neccesary that the modular inverse would exist with respect to m.

(please correct me if I am wrong)

No, for an array if we want to know for every number, the product of other numbers, we can achieve it by storing the prefix product and suffix product.

can you please elaborate more or share the link of your code

Here you go: submissiom

NOTE: My code is a little ugly.

![](https://i.imgur.com/2vVTfEs.jpg) Instead of dividing the product of the whole array by x, we can compute prefix * suffix

Can Someone explain What is rerooting?

In rerooting, what we basically do is first calculate the required data by considering some node as the root of the tree.

In rerooting type problems, it is required to calculate the same data by considering each and every node as the root, using naive approach would result in tle.

So, what we try do is using the calculated values(say by considering 1 to be the root), we try to calculate the answer for each node(if we assume that node to be the root) in O(1) time.

Consider a case in which

`node`

is the current root and`it`

is one of it's child, so`it`

would had contributed something in the answer of`node`

, so now we try to make`it`

as the new root, so first we remove the contribution of`it`

from`node`

, then`node`

is now a child for`it`

, so we add the contribution of the subtree with root being`node`

to the answer of`it`

and now`it`

has become the new root of the tree.But when we need to calculate the answer for say

`it1`

(second child of node) , we have to rollback the changes we made.The blog from where I learnt rerooting:-link

One more problem based on the concept : 1324F - Maximum White Subtree

766 E.

https://atcoder.jp/contests/abc160/tasks/abc160_f

https://atcoder.jp/contests/abc149/tasks/abc149_f

This link was really helpful

sorry brother i downvoted it by mistake so sorry for that

https://codeforces.com/contest/219/problem/D https://codeforces.com/problemset/problem/615/B

https://atcoder.jp/contests/abc160/tasks/abc160_f

https://atcoder.jp/contests/abc149/tasks/abc149_f

https://codeforces.com/contest/1187/problem/E

https://codeforces.com/contest/1092/problem/F

https://codeforces.com/contest/1324/problem/F

https://atcoder.jp/contests/dp/tasks/dp_v

https://codeforces.com/contest/960/problem/E

https://cses.fi/problemset/task/1132

https://cses.fi/problemset/task/1133

https://dmoj.ca/problem/dmopc14c4p6

https://oj.uz/problem/view/CEOI17_chase

https://dmoj.ca/problem/cco13p3

https://dmoj.ca/problem/coci08c1p6

Collected from various blogs. It might help.

This is quite a nice one!

More problems from recent ABCs that can be solved with rerooting:

https://atcoder.jp/contests/abc223/tasks/abc223_g

https://atcoder.jp/contests/abc222/tasks/abc222_f

https://atcoder.jp/contests/abc220/tasks/abc220_f

In particular abc222f's editorial has a nice generic template with links to (japanese) tutorials

Hello,

Actually I can't understand how to use merge and apply function

Like in your second question I am using

Data merge(Data a, Data b) { return a + b; }

and apply as

Data apply(Data a, int c, int d, Cost w) { return a + w; }

But this is wrong