PROBLEM LINK:
Author: Kirill Gulin
Tester: Mugurel Ionut Andreica
Editorialist: Kirill Gulin
PROBLEM
You’re given a tree with N nodes. Initially, each node has value 0. You’re to perform Q queries:
- v k a b: Consider f(0) = a, f(1) = b, f(i) = f(i - 1) + f(i - 2) for i \geq 2. For each node u of the tree, let d be the distance (in edges) from v to u. Then, if d \leq k, add f(d) to the value of node u.
- v: Print the value of node v modulo 10^9 + 7.
QUICK EXPLANATION
Decompose a tree using centroid decomposition. For each layer of the decomposition store binary indexed trees of pairs (a_i, b_i) with i-th element denoting each node of the layer on depth i is the i-th element of (a_i, b_i)-Fibonacci sequence. Use the fact that the sum of the n-th elements of the two Fibonacci sequences (a, b) and (c, d) is equal to the n-th element of the (a + c, b + d)-Fibonacci sequence.
EXPLANATION
Subtask 1 solution.
Suppose a query of the first type comes. Count the Fibonacci numbers for all i from 1 to N and the distance from node v to all nodes of the tree using dfs. Iterate over all the vertices, and if the distance from v to it does not exceed k add the corresponding Fibonacci number to its value. When a query of the second type comes, all the values of the nodes are already correct and therefore you can just output the required value.
Subtask 2 solution.
Initially, precalculate Fibonacci numbers in an array fib, assuming fib_0 = fib_1 = 1. We call the (a, b)-Fibonacci sequence generalized Fibonacci numbers with f(0) = a, f(1) = b, f(i) = f(i-1)+f(i-2) for i \geq 2. Then the n-th element f(n) of (a, b)-Fibonacci numbers can be calculated as follows: f(0)= a, f(1) = b, f(n) = a \cdot fib_{n-2} + b \cdot fib_{n-1}. One of the key ideas of the problem is that the sum of the n-th elements of the two Fibonacci sequences (a, b) and (c, d) is equal to the n-th element of the (a + c, b + d) Fibonacci sequence which immediately follows from the statement above
Use the standard divide-and-conquer approach on a tree called centroid decomposition. You can read more about centroid decomposition here. Find the centroid of the tree. The centroid of a tree is a such its node, when it is removed the remaining subtrees obtained have a size that at least two times less than size of the original tree. Such a node always exists and can be easily found in O(N) time, where N is a size of the original tree. Root the tree with this node and call such a tree a layer of decomposition. Remove this node from the tree and recursively do the same in the remaining trees. The set of all obtained layers is a centroid decomposition. It has some interesting properties:
- There are exactly N layers in the decomposition with each node of the tree as the root of exactly one of the layers.
- Each node of the tree belongs to O(\log N) decomposition layers since while descending recursively, we reduced the size of the tree at least by half.
- The total size of all layers is O(N\log N).
- For any path in the tree, there is exactly one decomposition layer such that this path exists entirely in it and passes through its root. This is a key property that allows you to solve the tasks with the paths in trees.
Suppose a query of first type comes, that is, it is need to add the d-th element of the (a, b)-Fibonacci sequence to all nodes at a distance d from the node v for each 0 \leq d \leq k. Consider all decomposition layers containing node v, there are O(log N) such layers. Each path with v as one of its endpoints contains the other endpoint u of the path in several of these layers, but exactly one of them contains this layer root on the path from v to u. Therefore, in order to avoid repeated updates of the values of node u, in each layer we need to update the values only of such nodes that contain the root of the layer on the path to v. It is easy to understand that if the root of a tree has some set of immediate sons, then the path from v to u does not pass through this root if both v and u belong to the same subtree of the root’s son.
Imagine a data structure that supports an array of k numbers, and can return the value of any element and perform addition of (a,b)-Fibonacci series on a prefix of the array, i.e. it can add i-th element of the (a, b)-Fibonacci sequence to the i-th element of array for each i not exceeding some p. To understand how to do this, consider the following problem: you must be able to add the number x on the interval [l; r] of some array and return the value of the i-th element of this array. It can be solved with the binary indexed tree (or with the segment tree) as follows. If a query of the first type comes, increase the value at the position l by x and at the position r by -x. Then the answer to the query at position i is just the sum of the values on the prefix of length i. Let’s understand how this works. If the query of the first type comes, then it must affect only the elements of the interval [l; r]. Let’s show that the operations performed are correct for calculations of the values in the position i. Suppose i < l, since we did not add anything before position l all the values remained unchanged. Now suppose l \leq i \leq r. Then x added at position l increases values on the whole interval [l;r] by x. Suppose r <i. Then adding x at the position l and -x at position r results into a zero balance for all i after r, like if we “canceled” the addition at position l. Thus, the changes affected only the desired segment, as it was necessary.
We will use a similar idea in our structure realization. Store the global pair (sa, sb), meaning that the i-th element can be found as the i-th element of the (sa, sb)-Fibonacci sequence. In order to add series only to the prefix of the array, we will store a binary indexed tree of pairs (a, b) (essentially two trees, one for a and another for b) in order to cancel the addition beyond the prefix. Therefore when the query for adding (a,b)-sequence to the prefix i comes, increase sa by a, sb by b and add the pair (a, b) in the position i + 1 of BIT. Then the value at the i-th position can be found as the i-th element of (pa, pb)-Fibonacci sequence, where pa = sa-sumAOnPrefix(idx), pb = sb - sumBOnPrefix(idx).
Store c + 1 such structures for each layer where c is the number of immediate sons of the root. One of the structures is for the whole layer and the remaining for each of the sons (sons’ structures are for cancelling additions between nodes in the same subtree, i.e. their path doesn’t pass layer’s root). Suppose query v k a b comes. Consider all the layers containing v and v is on depth d in this layer. Then add (p, q)-sequence to the prefix k-d (only if k \geq d) to the structures of the whole layer and the root’s son containing v (only if v is not the root of this layer), with p = d-th element of (a,b)-Fibonacci sequence and q = (d+1)-th its element. For answering the query, iterate over the layers containing v and add to the answer the value in the position d of the structure of the entire layer minus the value in the same position of the structure of the son to which v belongs to.
Since the operations with BIT take O(\log N) time in each of the O(\log N) layers of decomposition the overall time complexity is O(Q \log^2 N).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.