By S_Aditya, history, 3 years ago,

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.

• +5

 » 3 years ago, # |   0
 » 3 years ago, # |   0 thanks
 » 2 years ago, # |   0
•  » » 2 years ago, # ^ |   0 Well done, would you join our Clan!
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 ok (clan like some group for practicing algos and problems i assume).
•  » » » » 2 years ago, # ^ |   0
 » 2 years ago, # | ← Rev. 3 →   +5 1187E - Tree Painting One of the best problem on rerooting!!
 » 2 years ago, # |   +1 This comment have few more nice problems on rerooting.
 » 2 years ago, # |   +1 This one was fun to work out: https://codeforces.com/contest/960/problem/E
 » 2 years ago, # |   +16 this one: Atcoder dp_v
•  » » 2 years ago, # ^ |   0 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)
•  » » » 2 years ago, # ^ |   +19 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.
•  » » » » 2 years ago, # ^ |   0 can you please elaborate more or share the link of your code
•  » » » » » 2 years ago, # ^ |   +19 Here you go: submissiomNOTE: My code is a little ugly.
•  » » » » » 2 years ago, # ^ |   +19 ![](https://i.imgur.com/2vVTfEs.jpg) Instead of dividing the product of the whole array by x, we can compute prefix * suffix
 » 2 years ago, # |   +6 Can Someone explain What is rerooting?
•  » » 2 years ago, # ^ |   +5 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.
 » 2 years ago, # |   +2 The blog from where I learnt rerooting:-link
 » 2 years ago, # |   0 One more problem based on the concept : 1324F - Maximum White Subtree
 » 2 years ago, # |   0
 » 2 years ago, # |   0
 » 2 years ago, # |   0 This link was really helpful
 » 23 months ago, # |   0 sorry brother i downvoted it by mistake so sorry for that
 » 19 months ago, # | ← Rev. 2 →   0
 » 19 months ago, # | ← Rev. 3 →   +7
 » 18 months ago, # |   0 This is quite a nice one!
 » 7 months ago, # | ← Rev. 3 →   +6 More problems from recent ABCs that can be solved with rerooting:https://atcoder.jp/contests/abc223/tasks/abc223_ghttps://atcoder.jp/contests/abc222/tasks/abc222_fhttps://atcoder.jp/contests/abc220/tasks/abc220_fIn particular abc222f's editorial has a nice generic template with links to (japanese) tutorials
•  » » 7 months ago, # ^ |   0 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