Online Query Based Rerooting Technique

Revision en47, by DeadlyCritic, 2020-07-06 21:41:48

Halo :D!

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

Introduction

(Our DP changes if we change the root of the tree, otherwise it won't make any sense to use this trick)

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

Implementation

First, calculate DP when the root is some vertex $rat$. Its obvious that if we change root $r$ to one of its adjacent vertices, $v$, then only $dp_r$ and $dp_v$ can change, so that we can update $dp_r$ using its new children and last $dp_r$, also $dp_v$ can be updated the same way. It really depends on the DP.

Note:

Don't iterate over children of vertices when moving the root, it will be $O(\sum\limits_v\binom{d_v}{2})$ 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

I can't open some of the problems so there is no solution for them, sorry.

You can read the same trick here, also the site has some problems.

Problem2

Problem4

Please comment problems that can be solved using this trick.

Let's say that the problem has online queries, such that each query gives two vertices $r$ and $v$ and wants you to calculate $f(r, v)$, it's equal to $dp_v$ when the root is $r$. It can be solved with rerooting + ancestors binary lifting, it will answers each query in $O(Q*log_2n)$ time($O(log_2n)$ for binary lifting), and also $O(n*log_2n)$ precalculation.

So lets see how it works, for every edge($v \to u$) find $dp_v$ if the root is $u$ and $dp_u$ if the root is $v$, it will take $O(n)$ time and $O(n)$ memory, and also for each vertex $v$, store $f(v, v)$. Then 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 the answer will be $f(v, v)$, which is calculated in advance, otherwise the problem is reduced to the following problem:

You are given two vertices $r$ and $u$$(u \ne r)$ what is the second vertex in the unique path from $u$ to $r$(it means we want to find out which vertex is adjacent to $u$ and is the closest to $r$).

This problem can be solved using binary lifting, if $u$ is not an ancestor of $r$, then the answer is $u$'s parent(the root is vertex $rat$), otherwise, move $r$ using binary lifting until it's depth is equal to $u$'s depth plus 1, it can be done in $O(log_2n)$, let the answer to the reduced problem be $z$, then the answer to the whole query is equal to $f(z, u)$ such that $z$ is adjacent to $u$, we have already calculated it.

See the semi-code below, i skipped some parts so i will use $moveto(nw,\,u)$ to move the root from $nw$ to $u$, $f(r, u)$ for $dp_u$ when the root is $r$ and $rise(r,\,u)$ to find the ancestor of $r$ with depth equal to $depth_u+1$ in $O(log_2n)$.

Semi-code

I tried to add a problem from polygon for the advanced part, the problem is completed but I couldn't bring it to Codeforces, but I give you the link for problem's package, it includes 50 tests, validator and checker, main correct solution and problem statement, you can try running them in polygon.

Here is the complete implementation for the topic, $dp[u]$ is the size of the subtree of $u$ here.

Solution

I used map to store the data, so the solution is a little slower than expected.

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'