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.
In this blog post, I will describe a way to solve these types of problems using a DFS, a Fenwick tree, and LCA.
Prerequisites
- DFS
- Preorder traversal (DFS order)
- Fenwick tree
- Binary lifting and LCA
The idea
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$$$.
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 increment the range $$$[A, B]$$$ by $$$X$$$, 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$$$ 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 increment the value of node $$$u$$$ (or the value of the edge going to $$$u$$$'s parent) by $$$X$$$, we increase $$$BIT_{tin_u}$$$ by $$$X$$$ and decrease $$$BIT_{tout_u + 1}$$$ by $$$X$$$. Then when we want to find the sum of nodes/edges on the path between node $$$v$$$ and the root, we simply query the sum of $$$BIT_i$$$ from 0 to $$$tin_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$$$.
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:
- Delete the edge $$$(u, v)$$$ from the path.
- 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 our trick 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 also runs in $$$O(M \log N)$$$ time.
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
Conclusion
I hope you've learned something from this tutorial. If anything is unclear, please let me know in the comments below.
Additional problems
- COCI 2020 Putovanje
- SACO 2015 Towers (Doesn't use a Fenwick tree but has a similar idea)
