Persistent Rerooting Technique

Revision en18, by DeadlyCritic, 2020-04-17 14:47:28

Halo :D!

Story: It was 4AM and i was unable to sleep so i brought you a nice trick and couple of problems to practice it.

Introduction

(Our dp changes if we change root of the tree, otherwise it wont make any sens to use this trick)

Lets say we want to find $$$dp_v$$$ for every vertex in a tree, this dp must be updated using the children of vertex $$$v$$$. Then the trick allows you to move the root from a vertex to one of it's adjacent vertices in $$$O(1)$$$.

It will be much better if the problem wants you to move the root to all vertices and find maximum of dp-s or etc.

Implementation

First calculate dp for a root $$$rat$$$. Its obvious that if we change root $$$r$$$ to one of its adjacent vertex $$$v$$$, then only $$$dp_r$$$ and $$$dp_v$$$ can change, so that we can update $$$dp_r$$$ using its new children and past $$$dp_r$$$, also $$$dp_v$$$ can be updated the same way.

Note: Don't iterate over $$$r$$$ and $$$v$$$ children, it will be $$$O(\sum\limits_v\binom{d_v}{2})$$$ if you do it and $$$W(n^2)$$$ so just don't.($$$d_v$$$ is the degree of vertex $$$v$$$

Now being able to move the root with distance one, we will run a dfs from $$$rat$$$, and move the root with dfs.

See the semi-code below, i hope it helps for better understanding:

Semi-code

Problems

Problem1 Solution

Problem2//i cant open atcoder =(.

Problem3 Solution//this solution will be updated to highlight the trick

Problem4//again i cant see the problem but i believe i have solved it.

Problem5//no solution right now

Probelm6//no solution right now

Please comment the problems which can be solved using this trick.

Advanced

Lets say that the problem has queries, such that each query gives two vertices $$$r$$$ and $$$v$$$ and wants you to calculate $$$f(r, v)$$$, its equal to $$$dp_v$$$ when the root is $$$r$$$. It can be solved with rerooting + LCA, it will need additional $$$O(n)$$$ memory and answers each query in $$$O(Q*L)$$$ time(our LCA answers each query in $$$O(L)$$$ time).

So lets see how it works, for every vertex find it's dp if the root is one of it's children or itself and store them, it will take the time it takes to move the root around and an additional $$$O(n)$$$ memory at all. If the query is in form $$$v$$$ and $$$v$$$(i.e. it wants to find $$$dp_v$$$ such that the tree is rooted at vertex $$$v$$$ itself) then we have calculated so just print it, now the problem is decreased to the following problem, you are given two vertices $$$v$$$ and $$$u$$$, in the unique path from $$$v$$$ to $$$u$$$, $$$(u != v)$$$ what is the second vertex in the unique path from $$$v$$$ to $$$u$$$(it means we want to find out which child of $$$v$$$ is the closest to $$$u$$$), this part can be calculated using LCA(we say the root of the tree is vertex 1 for LCA), just find they're LCA, if it wasn't equal to $$$v$$$, then the answer is $$$v$$$'s parent(the root is vertex 1), otherwise move $$$u$$$ using binary lifting until it's depth is equal to $$$v$$$'s depth plus 1, it can be done in $$$O(log_2n)$$$, lets call the answer of the reduced problem, $$$z$$$, then the answer is equal to $$$f(z, v)$$$ we have precalculated this value so just print it :).

I hope it will help you with solving DP-Tree problems, the implementation will be added.

Thanks for your attention.

Tags #dp, tree_dp, trick, #dfs and similar, rerooting technique, persistent structures, persistent, #data structure

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en48 English DeadlyCritic 2022-01-09 07:09:59 258 Tiny change: 'n\n[link](codeforces' -> 'n\n[link](https://codeforces'
en47 English DeadlyCritic 2020-07-06 21:41:48 231
en46 English DeadlyCritic 2020-05-24 09:45:09 756
en45 English DeadlyCritic 2020-04-19 17:30:36 139
en44 English DeadlyCritic 2020-04-19 00:20:52 72
en43 English DeadlyCritic 2020-04-19 00:12:43 80
en42 English DeadlyCritic 2020-04-19 00:10:39 218
en41 English DeadlyCritic 2020-04-19 00:04:22 56
en40 English DeadlyCritic 2020-04-19 00:02:14 38
en39 English DeadlyCritic 2020-04-19 00:00:38 10 Tiny change: 'this will calculate move the ' -> 'this will move the '
en38 English DeadlyCritic 2020-04-18 23:59:56 15
en37 English DeadlyCritic 2020-04-18 23:58:30 9
en36 English DeadlyCritic 2020-04-18 23:56:03 2 Tiny change: 'ry edge($v\tou$) find $' -> 'ry edge($v \to u$) find $'
en35 English DeadlyCritic 2020-04-18 18:32:50 66
en34 English DeadlyCritic 2020-04-18 18:30:04 4 Tiny change: 'ry edge($v$ \to $u$) find $' -> 'ry edge($v\tou$) find $'
en33 English DeadlyCritic 2020-04-18 18:29:17 1 Tiny change: '$O(log_2n) for binar' -> '$O(log_2n)$ for binar'
en32 English DeadlyCritic 2020-04-18 18:19:01 86
en31 English DeadlyCritic 2020-04-18 18:16:23 8999
en30 English DeadlyCritic 2020-04-18 18:00:57 99
en29 English DeadlyCritic 2020-04-18 17:50:12 484
en28 English DeadlyCritic 2020-04-18 17:42:25 688
en27 English DeadlyCritic 2020-04-18 17:09:46 97
en26 English DeadlyCritic 2020-04-18 12:25:14 136
en25 English DeadlyCritic 2020-04-17 23:52:30 238
en24 English DeadlyCritic 2020-04-17 23:37:39 77
en23 English DeadlyCritic 2020-04-17 23:35:38 34 Tiny change: 'e problems, the implementation will be added.\n\nThank' -> 'e problems.\n\nThank'
en22 English DeadlyCritic 2020-04-17 23:35:11 1642
en21 English DeadlyCritic 2020-04-17 19:02:21 4
en20 English DeadlyCritic 2020-04-17 15:27:10 13
en19 English DeadlyCritic 2020-04-17 14:56:11 307 Tiny change: 'nd $u$$(u != v)$ what ' -> 'nd $u$$(u \ne v)$ what '
en18 English DeadlyCritic 2020-04-17 14:47:28 1599
en17 English DeadlyCritic 2020-04-17 12:42:25 3 Tiny change: '/abc160_f)\n///i cant o' -> '/abc160_f)//i cant o'
en16 English DeadlyCritic 2020-04-17 12:41:50 110
en15 English DeadlyCritic 2020-04-17 12:39:01 18 Tiny change: 'e way.\n\n$\binom{4}{2}$\n\n*Note:' -> 'e way.\n\n*Note:'
en14 English DeadlyCritic 2020-04-17 12:38:07 252 Tiny change: 'e way.\n\n*Note:' -> 'e way.\n\n$\binom{4}{2}$\n\n*Note:'
en13 English DeadlyCritic 2020-04-17 12:27:58 284
en12 English DeadlyCritic 2020-04-17 12:16:32 290
en11 English DeadlyCritic 2020-04-17 05:05:12 147
en10 English DeadlyCritic 2020-04-17 05:01:51 94
en9 English DeadlyCritic 2020-04-17 04:46:45 66 Tiny change: 'tions\n\n[halo](https://' -> 'tions\n\n[Tree Painting](https://'
en8 English DeadlyCritic 2020-04-17 03:54:24 601
en7 English DeadlyCritic 2020-04-17 03:46:53 20 Tiny change: ' Hi,\n Its 4AM ' -> ' Hi,\n Its 4AM '
en6 English DeadlyCritic 2020-04-17 03:43:46 20
en5 English DeadlyCritic 2020-04-17 03:41:57 12 Tiny change: 'low me to right it in wor' -> 'low me to --right-- write it in wor'
en4 English DeadlyCritic 2020-04-17 03:11:25 35
en3 English DeadlyCritic 2020-04-17 03:08:14 2 Tiny change: 'rks in $O(t)$ to calc' -> 'rks in $O(T)$ to calc'
en2 English DeadlyCritic 2020-04-17 03:07:48 156 (published)
en1 English DeadlyCritic 2020-04-17 03:05:35 2061 Initial revision (saved to drafts)