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 | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
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.
Name |
---|
Codeforces Round #527 (Div. 3) Problem F
thanks
https://codeforces.net/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.net/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 andit
is one of it's child, soit
would had contributed something in the answer ofnode
, so now we try to makeit
as the new root, so first we remove the contribution ofit
fromnode
, thennode
is now a child forit
, so we add the contribution of the subtree with root beingnode
to the answer ofit
and nowit
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
https://codeforces.net/contest/219/problem/D https://codeforces.net/problemset/problem/615/B
https://atcoder.jp/contests/abc160/tasks/abc160_f
https://atcoder.jp/contests/abc149/tasks/abc149_f
https://codeforces.net/contest/1187/problem/E
https://codeforces.net/contest/1092/problem/F
https://codeforces.net/contest/1324/problem/F
https://atcoder.jp/contests/dp/tasks/dp_v
https://codeforces.net/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