PROBLEM LINK:
Author: Zi Song Yeoh
DIFFICULTY:
MEDIUM
PREREQUISITES:
Tree DP, Small-to-Big Technique, DSU, LCA
PROBLEM:
Answer dynamic weighted distance query on a tree online. (Dynamic in this case means that we can add edges to the graph such that no cycles are formed)
EXPLANATION:
The first subtask can be done in O(nq) by just simulating all the operations naively.
The second subtask can be solved in O((n + q)\log n). The key is that in this subtask, we can just build the whole tree first and then answer all the distance queries. The tree distance queries on a static tree is a well-known problem and can be solved using Sparse Table and LCA for instance.
The third subtask is an extension of subtask 2. Now, you have to answer the queries in real-time while the edges are being added. We will store a sparse table for each node denoting the 2^{k}-th parent and the sum of all edges on the way to this parent. Now, when we join two vertices from distinct trees in the current forest, we will join the smaller tree to the larger tree and recalculate the sparse table for the smaller tree. You can see the details in the code. This allows us to solve the problem in O((n + q)log^{2}n) time.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.