Rerooting Technique

Revision en17, by DeadlyCritic, 2020-04-17 12:42:25

Halo,

Story: Its 4AM here and i cant 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

#### Applications

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.

#### History

Revisions

Rev. Lang. By When Δ Comment
en36 DeadlyCritic 2020-04-18 23:56:03 2 Tiny change: 'ry edge($v\tou$) find $' -> 'ry edge($v \to u$) find$'
en34 DeadlyCritic 2020-04-18 18:30:04 4 Tiny change: 'ry edge($v$ \to $u$) find $' -> 'ry edge($v\tou$) find$'
en33 DeadlyCritic 2020-04-18 18:29:17 1 Tiny change: '$O(log_2n) for binar' -> '$O(log_2n)$for binar' en32 DeadlyCritic 2020-04-18 18:19:01 86 en31 DeadlyCritic 2020-04-18 18:16:23 8999 en30 DeadlyCritic 2020-04-18 18:00:57 99 en29 DeadlyCritic 2020-04-18 17:50:12 484 en28 DeadlyCritic 2020-04-18 17:42:25 688 en27 DeadlyCritic 2020-04-18 17:09:46 97 en26 DeadlyCritic 2020-04-18 12:25:14 136 en25 DeadlyCritic 2020-04-17 23:52:30 238 en24 DeadlyCritic 2020-04-17 23:37:39 77 en23 DeadlyCritic 2020-04-17 23:35:38 34 Tiny change: 'e problems, the implementation will be added.\n\nThank' -> 'e problems.\n\nThank' en22 DeadlyCritic 2020-04-17 23:35:11 1642 en21 DeadlyCritic 2020-04-17 19:02:21 4 en20 DeadlyCritic 2020-04-17 15:27:10 13 en19 DeadlyCritic 2020-04-17 14:56:11 307 Tiny change: 'nd$u$$(u != v) what ' -> 'nd u$$(u \ne v)$what ' en18 DeadlyCritic 2020-04-17 14:47:28 1599 en17 DeadlyCritic 2020-04-17 12:42:25 3 Tiny change: '/abc160_f)\n///i cant o' -> '/abc160_f)//i cant o' en16 DeadlyCritic 2020-04-17 12:41:50 110 en15 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 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 DeadlyCritic 2020-04-17 12:27:58 284 en12 DeadlyCritic 2020-04-17 12:16:32 290 en11 DeadlyCritic 2020-04-17 05:05:12 147 en10 DeadlyCritic 2020-04-17 05:01:51 94 en9 DeadlyCritic 2020-04-17 04:46:45 66 Tiny change: 'tions\n\n[halo](https://' -> 'tions\n\n[Tree Painting](https://' en8 DeadlyCritic 2020-04-17 03:54:24 601 en7 DeadlyCritic 2020-04-17 03:46:53 20 Tiny change: ' Hi,\n Its 4AM ' -> ' Hi,\n Its 4AM ' en6 DeadlyCritic 2020-04-17 03:43:46 20 en5 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 DeadlyCritic 2020-04-17 03:11:25 35 en3 DeadlyCritic 2020-04-17 03:08:14 2 Tiny change: 'rks in$O(t)$to calc' -> 'rks in$O(T)\$ to calc'