dolphingarlic's blog

By dolphingarlic, history, 4 years ago, In English

Introduction

I've come across several problems that require you to be able to efficiently find the sum of some values on a path from $$$A$$$ to $$$B$$$ in a tree. One can solve these problems using tree decomposition techniques like heavy-light decomposition or centroid decomposition, but that's a bit of an overkill and not very elegant in my opinion.

In this blog post, I will describe a way to solve these types of problems using just a DFS, a Fenwick tree, and LCA (as well as a way to solve JOIOC 2013 Synchronization this way).

Note: Whenever I talk about edge $$$(u, v)$$$ in this post, I assume that $$$u$$$ is the parent of $$$v$$$.

Prerequisites

  • DFS
  • Preorder traversal (DFS order)
  • Fenwick tree
  • Binary lifting and LCA

The idea

Say you have the following problem:

Given a tree with $$$N$$$ nodes, each node $$$i$$$ has a value $$$a_i$$$ that is initially 0. Support the following 2 types of operations in $$$O(\log N)$$$ time:

  1. Increase the value of $$$a_i$$$ by $$$X$$$
  2. Find the sum of $$$a_i$$$ on the path from $$$u$$$ to $$$v$$$ for 2 nodes $$$u$$$ and $$$v$$$

First, we flatten the tree using a preorder traversal. Let the time we enter node $$$i$$$ be $$$tin_i$$$ and the time we exit it be $$$tout_i$$$. Additionally, let $$$b$$$ be an array/Fenwick tree of size $$$2N$$$.

If you're familiar with LCA, you'll know that node $$$u$$$ is an ancestor of node $$$v$$$ if and only if $$$tin_u \leq tin_v$$$ and $$$tout_u \geq tout_v$$$.

If you're familiar with range updates and point queries with Fenwick trees, you'll know that if we want to increase the range $$$[A, B]$$$ by $$$X$$$ in an array/Fenwick tree $$$BIT$$$, then we increase $$$BIT[A]$$$ by $$$X$$$ and decrease $$$BIT[B + 1]$$$ by $$$X$$$. Then when we want to find the value of the element at $$$C$$$, we simply query the sum of $$$BIT[i]$$$ for each $$$i$$$ from 0 to $$$C$$$. This works because if $$$C$$$ isn't inside the range of an update, the 2 values we update "cancel out" in the query.

We can combine the 2 ideas above to work on trees — if we want to increase the value of node $$$u$$$ by $$$X$$$, we increase $$$b[tin_u]$$$ by $$$X$$$ and decrease $$$b[tout_u + 1]$$$ by $$$X$$$. Then when we want to find the sum of nodes on the path between node $$$v$$$ and the root, we simply query the sum of $$$b[i]$$$ for each $$$i$$$ from 0 to $$$tin_v$$$. This works because node $$$w$$$ only contributes to the sum if $$$w$$$ is an ancestor of $$$v$$$.

We can then use LCA and the principle of inclusion-exclusion to find the sum of nodes/edges on the path between nodes $$$u$$$ and $$$v$$$.

This idea also works if we want to sum edges instead of nodes — when we update edge $$$(u, v)$$$, update $$$b[tin_v]$$$ and $$$b[tout_v + 1]$$$ and make queries similarly.

Problem 1 — Infoarena Disconnect

Here's the gist of the problem:

You're given a tree with $$$N$$$ nodes. Process $$$M$$$ of the following queries online:

  1. Delete the edge $$$(u, v)$$$ from the path.
  2. Determine whether there is a path from $$$u$$$ to $$$v$$$.

$$$N \leq 10^5$$$ and $$$M \leq 5 \cdot 10^5$$$

Solution

Let the value of each edge in the tree initially be 0. When we "delete" an edge, we just update its value to be 1.

Notice how there is a path from $$$u$$$ to $$$v$$$ if and only if the sum of edges on the path between $$$u$$$ and $$$v$$$ is 0.

We can then apply the above idea and solve this problem in $$$O(M \log N)$$$ time.

Alternatively,

  • Find the lowest ancestor $$$l_u$$$ of $$$u$$$ such that the sum of the edges between $$$u$$$ and $$$l_u$$$ is 0
  • We can do this using binary lifting and our trick
  • Find $$$l_v$$$ similarly for $$$v$$$.
  • Check whether $$$l_u$$$ is an ancestor of $$$v$$$ and whether $$$l_v$$$ is an ancestor of $$$u$$$.

This solution runs in $$$O(M \log^2 N)$$$ time.

My code for this problem

Problem 2 — JOIOC 2013 Synchronization

Here's the gist of the problem:

You're given a tree with $$$N$$$ nodes. Each edge is initially deactivated and each node stores a unique piece of information.

There are $$$M$$$ events. During event $$$i$$$, the state of exactly 1 edge is toggled.

When the edge $$$(u, v)$$$ becomes activated, $$$u$$$'s component and $$$v$$$'s component merge and "sync up". All nodes in the merged component will contain all the information stored on the other nodes in the component.

After all these events, you want to know how many unique pieces of information are stored in each node.

$$$N \leq 10^5$$$ and $$$M \leq 2 \cdot 10^5$$$

Solution

Firstly, root the tree arbitrarily. Let $$$a_i$$$ be the amount of unique information stored on node $$$i$$$. Let $$$c_i$$$ be the amount of unique information stored on node $$$i$$$ right before the edge from node $$$i$$$ to its parent was deactivated.

Notice how if we make the edge $$$(u, v)$$$ activated, then the new amount of information on all nodes in the merged component is $$$a_u + a_v - c_v$$$.

This gives us a way to find the amount of information on the merged component, but we still need a way to set each node in the component to have that amount of information.

Fortunately, we don't have to do that!

Since each node in a component has the same amount of information, we can just store that amount in the "root" (i.e. the lowest node) of the component. Let the root of $$$i$$$'s component be $$$root[i]$$$. The amount of information stored on $$$i$$$ is thus $$$a_{root[i]}$$$.

When we deactivate the edge $$$(u, v)$$$, $$$v$$$ becomes the root of its new component and $$$root[u]$$$ doesn't change. This means we can simply set $$$a_v$$$ and $$$c_v$$$ to equal $$$a_{root[u]}$$$ when that happens (we don't care what $$$a_v$$$ and $$$c_v$$$ were before this).

But how do we find the root of a component?

$$$root_u$$$ is the lowest ancestor of $$$u$$$ such that the path from $$$u$$$ to $$$root_u$$$ contains no deactivated edges. We can thus use the same idea we used for the previous problem, but this time, all edges initially have their weight equal to 1 instead of 0.

Using binary lifting, we can find the root of any component in $$$O(\log^2 N)$$$ time.

This solution runs in $$$O(M \log^2 N)$$$ time.

My code for this problem

Conclusion

I hope you've learned something from this tutorial. If anything is unclear, please let me know in the comments below.

Additional problems

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

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

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

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

"JOI 2015 Railroad but on a general tree instead of a line" Is this a generalization of a particular problem? Which problem is this a generalization of?

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

Can we modify this to work for subtree updates as well? For example, if we wanted to add $$$X$$$ to the subtree of $$$a_i$$$ in $$$O(\log N)$$$ time?

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

Can't you calculate the sum of ranges along with binary lifting?
Example: 80876049 (here the maximum is required instead of the sum, but the idea is identical)
rm[u][k] = max(rm[u][k - 1], rm[parent[u][k - 1]][k - 1]); calculates the maximum in a range of length $$$2^k$$$.

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

    You could do that if there are no updates, but I don't think there's an easy way to handle updates without a Fenwick tree

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

Not to be a pain in the ass or anything but this is the same idea as Mo on trees

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

    Yeah but I think it's kinda nice how this post talks about queries when you add / remove edges from a tree (I don't think that is mentioned in the linked post)

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

    Am I mistaken, as the approaches feels different to me as Mo on trees relies on modified dfs traversal, the other uses the normal preorder array, the MO one is more generalized also.

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

Can anybody look at my code of problem 1: Infoarena Disconnect and tell my why this code gives TLE for the last 6 test cases? Ideone.

My code is supposed to work in $$$O(n log n)$$$ as you see it. A weird thing is when I set $$$z = u$$$ and not use LCA then it runs only $$$600ms$$$ (but WA obviously).

Thanks <3.

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

    OK I got AC :<. But by switching $$$pa[17][100001] -> pa[100001][17]$$$. Can anybody tell me why :<. It's really weird as I read somewhere someone told that $$$pa[17][100001]$$$ should be faster.

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

      Statements like 'this is faster than that' are usually only valid in certain contexts. Always try to remember which those are. Otherwise they are mere assumptions.

      Multidimensional arrays shall always be accessed by first iterating over the right-most index. In your code, you have lots of hot loops iterating from 1 to 16 or similar. With pa[17][100001], two consecutive accesses lead to a cache miss each time since the accessed memory locations are 100001 * sizeof(int) bytes apart. With the sizes swapped, you are accessing the bytes in sequence (at least in a forward loop, backwards pre-fetching depends on the smartness of the compiler).

      I am surprised, that it makes such a difference. Optimizations like these should be thoroughly benchmarked before making any claims, let alone going into production.

»
4 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it
int a = x ^ v, b = y ^ v;

dolphingarlic or someone: What exactly is being done here (in the solution for Problem 1)? I don't quite get what the xor's are doing here. Is v necessary?

EDIT: didn't read the problem statement carefully enough, my bad

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

I see that USACO 2015 Max Flow is cited as an additional problem. Is it possible to do that using the technique mentioned in the post? Seems like a different kind of problem (since you're updating paths rather than points). I can think of a solution that uses HLD + Fenwick, but I'm curious to see if there is a solution that uses the technique in the post.

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

    The idea of that problem is to count the amount each edge contributes to the answer.

    If you only update tin[i] instead of both tin[i] and tout[i], you can get the subtree sum by querying the range [tin[i], tout[i]]. Consider some path A--B. If you increase tin[A] and tin[B] by 1 and decrease tin[lca(A, B)] by 2, then only nodes on the path A--B get that +1 when you query their subtree sums.

    The COCI problem uses a similar idea.

    (Upon writing this, I realize I should've mentioned this technique in the post as well)

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

      Doesn't lca(A, B) get +0 in this case (if you query the subtree sum from [tin[lca(A, B)], tout[lca(A, B)]])?

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

      EDIT:

      I tried the following instead (as this forces +1 to be contributed to the LCA):

      int l = lca(u, v);
      update(tin[u], +1);
      update(tin[v], +1);
      update(tout[l], -1);
      update(tin[l], -1);
      

      And query the max over the sums in [tin[u], tout[u] — 1]

      I was able to get AC! https://pastebin.com/X6ASEEvg

      Also in case anyone is curious, here is my HLD + BIT solution (which also got AC): https://pastebin.com/duZ3cjPR

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

The problem Ball Machine from BOI2013 can be solved using a similar idea.

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

Nice Tutorial.Hope I have learnt something new and interesting.