AndreyPavlov's blog

By AndreyPavlov, history, 2 years ago, In English

Problem

When you learn about Heavy Light Decomposition tree problems take on new meaning. But writing HLD every tree problem with queries so boring. In this post, I will show some problems (as well as ideas for solving them) in which you can write HLD, but with a little thought, the solution becomes easier.

Modifications and receiving at the point

Task: A tree is given, as well as requests to add in a subtree and on the path to the root, as well as to find out the value at the top.

First idea — HLD! But stop, we only need the value at the point, maybe can easier? Yes, we will solve task in offline mode.

Idea: How to find out what changes occurred at the top at time $$$t$$$? Need to store some structure, for example, segment tree and answer for query in time $$$t$$$ is sum on prefix $$$t$$$. Now we have add in subtree and on the path to the root. For subtere adding we will remember for each vertex that in its subtree we need to add the number $$$x$$$ and the query time. Also for path adding we will remember this. Now we run the dfs on this tree with next algorithm:

  1. Checking all subtree addings and remember in segment tree with adding in point $$$t$$$ value $$$x$$$
  2. Go to the childs with dfs
  3. Checking all paths to the root adding and remember as well as in 1
  4. Get the answer on all queries with sum on prefix $$$t$$$
  5. Remove all subtree addings (add $$$-x$$$ on prefix $$$t$$$)

DFS implementation:

// ...
void dfs (int u, int p) {
    for (auto [t, x]: subtree_query[u]) {
        segment_tree.upd(t, x);
    }
    for (int child: graph[u]) {
        if (child != p) {        
            dfs(child, u);
        }
    }
    for (auto [x, t]: path_root_query[u]) {
        segment_tree.upd(t, x);
    }
    for (auto t: query[u]) {
        answer[t] = segment_tree.get(0, t);
    }
    for (auto [t, x]: subtree_query[u]) {
        segment_tree.upd(t, -x);
    }
}
// ...

NOTE: instead of a segment tree, you can use a fenwick tree

Asymptotics is $$$O(n + q \cdot log{q})$$$

Adding on path, get the value at the point

Task: Given a tree and given queries to add x on the path and get the value at the point. Sounds like a normal task on HLD, because we need to add on path of two vertex. But here you can do without hld.

Idea: Find the LCA of 2 vertex, call it $$$l$$$. We will be again work in offline mode, we know of query his time $$$t$$$. First we solve the problem, if first there are change requests and then get requests at the point. We will make next trick — we create a new array let's call him $$$a$$$ add $$$-1$$$ to $$$a_l$$$ and parent of $$$l$$$, add $$$1$$$ to $$$a_u$$$ and $$$a_v$$$. Next we run dfs on this tree and for every vertex $$$u$$$ count $$$\sum{a_i}$$$ where $$$i$$$ is vertex in subtree of $$$u$$$. Note that this sum will be equal to the number that will be written at the top after all requests. How to solve our originially problem? Let's add a segment tree for time $$$t$$$ just like you did in the previous task.

DFS implementation:

// ...
void dfs (int u) {
    for (auto [t, x]: subtree_query[u]) {
        segment_tree.upd(t, x);
    }
    for (int child: graph[u]) {
        if (child != p[u]) {        
            dfs(child);
        }
    }
    for (auto t: query[u]) {
        answer[t] = segment_tree.get(0, t);
    }
}
// ...
void add (int u, int v, int t) {
    int l = lca(u, v);
    subtree_query[l].push_back({t, -1});
    subtree_query[p[l]].push_back({t, -1});
    subtree_query[u].push_back({t, 1});
    subtree_query[v].push_back({t, 1});
}

Note: we also may change segment tree on fenwick tree

Asymptotics $$$O(n + q \cdot log{q})$$$

Tasks

D. Water Tree — assign $$$1$$$ on subtree, $$$0$$$ on path to root and get the value in point.

C. Propagating tree — add alternating sum to subtree and get the value at point.

E. Vasya and a Tree — add $$$x$$$ to the subtree $$$k$$$ level and output all values after.

A. Max Flow — add $$$1$$$ on path and output max vertex value

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

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

Auto comment: topic has been updated by AndreyPavlov (previous revision, new revision, compare).

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

Auto comment: topic has been updated by AndreyPavlov (previous revision, new revision, compare).

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

Auto comment: topic has been updated by AndreyPavlov (previous revision, new revision, compare).

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

D was tougher than E but overall question was well designed , i enjoyed it.

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

    D — implementation wise — was very easy. Just the logic was a bit hard but being from math background i didn't find it difficult. What i really struggled with and ultimately didn't solve in the end was problem C, the string question. How to solve?

»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Interesting post! I do have a few questions.

  1. In the first section "Modifications and receiving at the point", how does path_root_query in your pseudocode work? It seems you apply the update from root to $$$u$$$ once you dfs down to $$$u$$$, but that seems like the wrong time to apply the update, because then it doesn't affect the ancestors of $$$u$$$ which is what we really want? I'm thinking that we should instead $$$+x$$$ initially and then $$$-x$$$ when we reach $$$u$$$, but the issue is we would also have to $$$-x$$$ whenever we veer off the path (i.e. we dfs from some ancestor of $$$u$$$ to some node that isn't an ancestor of $$$u$$$), so this seems like a tricky operation to handle in the offline dfs model.
  2. In the second section "Adding on path, get the value at the point", if we add $$$-1$$$ to $$$l$$$ and $$$p[l]$$$ and $$$+1$$$ to $$$u$$$ and $$$v$$$ and apply updates in a top-down fashion per the pseudocode, isn't the overall effect adding $$$-2$$$ to most vertices on the path between $$$u$$$ and $$$v$$$? The pseudocode also differs from your text explanation which does it in a bottom-up order by accumulating all updates in the subtree which does give us the desired effect; the pseudocode appears to be doing top-down similar to section 1.
  3. But also, speaking of the text explanation of section 2, I'm not sure how you preserve both dimensions time and subtree sum without devolving to $$$\log^2 n$$$ or using something like this for single log. The example problem you linked for this trick, Max Flow, only does point queries after applying all updates, but the mention of time in the explanation seems to suggest we can also intertwine point queries and path updates in between each other.
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. Yep, this is error. The initial task was to assign on the way to the root, where it was necessary to write the transfusion technique, in this section I made a mistake with the addition.
    2. This works because we will add +x to the ancestors of u, v until we reach the lca ancestor, where we need to end the adding.
    3. We contain segment_tree in global and updating his in dfs, this is q log q
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it
      1. Ok.
      2. I get that, but I was saying the pseudocode doesn't match what the paragraph describes. The pseudocode goes top down. It will reach $$$l$$$ and $$$p[l]$$$ before $$$u$$$ and $$$v$$$, so we first $$$-x$$$ and then $$$+x$$$ as we move down in the dfs.
      3. The segment tree is built on time right? But what's stored in the segment tree is the values we've accumulated when moving down from root to node $$$u$$$ instead of the contents of the subtree $$$u$$$, which is what I thought we wanted.
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

A great blog, thanks a lot!