DeadlyCritic's blog

By DeadlyCritic, history, 4 years ago, In English

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.

Problem1 Solution

Problem2

Problem3 Solution

Problem4

Problem5 Solution

Probelm6 Solution

Please comment problems that can be solved using this trick.

Advanced

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 link to a group, where I added the mashup which contains the problem:

link

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.

I hope it will help you with solving DP-Tree problems.

Thanks for your attention.

  • Vote: I like it
  • +94
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it +27 Vote: I do not like it

Is this called the rerooting technique?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is it known?, i don't know too many algorithms, i just make them by myself when solving problems.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      tfw you invent something only to find out it is already invented...

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -6 Vote: I do not like it

        Yes something like this :), not only to find out its already invented but also to avoid reading lots of algorithms and techniques. Don't you think inventing already invented things helps you invent new things?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it -13 Vote: I do not like it

    Thanks for the call.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    In functional programming this is called a zipper. If you implement it in a pure functional style, you’ll get a persistent data structure. That is, not only you can move the root around, you can also store and have all the rerootings at the same time once you finish your DFS.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Seems interesting, I've never heard of such data structure can you share implementation?

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Thanks for the comment, i thought about how to build such data structure and i came up with rerooting + LCA that can handle online queries. Queries are two vertices $$$r$$$ and $$$v$$$, we have to print $$$f(r, v)$$$, it means $$$dp_v$$$ if $$$r$$$ is the root, this application will be added soon, please comment here if you know some problems which can be solved using the method.

      My solution works with $$$O(n)$$$ memory for data structure and $$$O(n*log_2n)$$$ memory for LCA, and answers each query in $$$O(T)$$$(if the LCA works in $$$O(T)$$$ time).

»
4 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Well, I read through as soon as you posted but haven't understood much (it's a good read tho). Need to watch more of William Fiset ig to begin with. It's 06:15 AM here and I can feel you hehe. Have been sleeping after 6 or 7 in the morning on average during this quarantine. Wake up after noon and binge netflix or rewatch interstellar for the umpteenth time. That's been my schedule (but I've also been taking out time and studying more of Graphs recently). How's it going for you?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Nice life you got :), closely the same but with more studying, and playing games as well, its not like i always sleep late, but today and only today just because i cant sleep.

»
4 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

Recently I've seen such problems on Atcoder & Codeforces contest

https://codeforces.com/contest/1187/problem/E
https://atcoder.jp/contests/abc160/tasks/abc160_f

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    Thanks for the links :D, nice problems thanks.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Somehow before seeing the first problem i came up with quite the same problem, the answer was $$$\displaystyle\sum\limits_{root}\sum\limits_{v}sz_v$$$ in my problem, where $$$sz_v$$$ means size of subtree of $$$v$$$, but here the answer is $$$\displaystyle\max\limits_{root}\sum\limits_{v}sz_v$$$.

»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's a well known trick and you should've known that if you read the editorial of any of the problems.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are right, i usually read editorials but i didn't know that it has a name at all, so probable its not that much well-known along div.2 participants.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The advanced part is added, i hope you find it useful.

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I really like this technique, which I know as Tree walk trick. There are a few more problems on AlgoWiki.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You welcome, Thank you.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Problem B from this contest can also be solved using Tree Walk Trick.

    Spoiler
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Thanks for the problem, unfortunately the contest neither has English statement nor Russian statement, so there is no way i can see the problem.

      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Oh, I'm so sorry! I forgot to mention that the pdf with the statements is given in the announcements section of the contest. You can see it here.

»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Was that intended to be hola?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice work! XD

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

The advanced part is for Online queries? If queries are given beforehand then we cal calculate it without advanced part. DeadlyCritic Am I correct?

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

DeadlyCritic How to solve this using rerooting? I am facing problem in finding the inverse of a number mod M, because for inverse to exist they should be relatively prime. But we are not sure if this condition is satisfied for every number?

  • »
    »
    4 years ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    I solved it using rerooting, here it is :

    First, calculate $$$dp_v$$$ for each vertex, where $$$dp_v$$$ is the number of ways to color some of the vertices in the subtree of $$$v$$$ such that $$$v$$$ is black as well. Also, it's easy to see that $$$dp_v$$$ is equal to product of $$$dp_c+1$$$ for all vertices $$$c$$$ that are exact children of $$$v$$$. (if $$$v$$$ has no child, then $$$dp_v = 1$$$)

    Now let $$$ans_v$$$ be the answer for $$$v$$$, it's easy to see that $$$ans_v = \frac {ans_p}{dp_v+1} \cdot dp_v$$$, where $$$p$$$ is the parent of $$$v$$$. This can be calculated using rerooting $$$+$$$ prefix product. (if $$$v$$$ is the root, then $$$ans_v = dp_v$$$)

    Tell me if you still can't solve it.

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you provide your submission link pls?

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      DeadlyCritic, In this problem, ansv needs to be stored modulo M. But, particularly in this task, M can be any integer in the range [2,109]. It would've been trivial if M would've been any prime integer, but how do you calculate the inverse of dpv+1 now?

      UPD: I understand it now. Thanks.

      For anyone who'd like to see how exactly prefix products help us here can view this submission.

      V-Subtree submission

»
2 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Excuse me, the link to the problem of the advanced technique didn't work.

Could you update it? Thanks.