PROBLEM LINK:
Author: Anudeep Nekkanti
Tester: Sergey Kulik
Editorialist: Lalit Kundu
DIFFICULTY:
HARD
PREREQUISITES:
Graphs, Trees, Data Structures, Segment Trees
PROBLEM:
Given an tree with N nodes. Each node has an value assigned.
Support following operations.
1) Add a child node to a node PARENT(Input) and assign it a given value
2) Remove a node and its subtree from the tree, Tree is unidirectional, rooted at 0
3) Update key values of all the subtree of a node by X
4) Answer the sum of keyvalues of subtree hanging at node X(Input)
EXPLANATION:
Offline Solution:
We shall discuss the offline solution which inturn gives idea for online solution.
Scan all the input, add all the nodes in the input with an initial value of 0, this will not change the problem.
Build the intime, outtime linearization of tree. Now every query for subtree is a contingious subarray. Initially all the node values be 0. We shall have an update function, that will activate a node and set its key value.
Now for the n nodes in input, activate them right away.
Now process the m queries, activate required nodes on the go. Other 3 functions we need are query, updateRange and killRange. updateRange can be done with lazy decomposition, killRange can also be done with lazy decomposition or we can also use the fact that any killed range will either be completely included or not at all included in next following queries.
For this solution to work we need all the input data at the begining of the queries.
In order to avoid OFFLINE SOLUTIONs we encoded the input to depend on previous QUERY answers.
We have an nodeKey in all 4 types of queries, we provide x-SPECIAL instead of x. we have a variable say SPECIAL, initially assigned to 0, when ever an answer query occurs, SPECIAL is updated to the output of that query. This will make sure that only ONLINE SOLUTIONS are used.
Online Solution:
We do not have data about further nodes that will be added.
If we want to follow the same solution described for OFFLINE SOLUTION, we will have to maintain segment trees which will support insertion of elements.
So, we keep a binary tree, where each node represents the nodes of the array (formed by linearization of the original tree in the problem). We keep the sum of all nodes in subtree at every node. So that we can answer the sum queries.
Always have a balanced binary tree, root will be roughly middle element always, and indexes [0…n/2] will be to left of root, and other right or root and like wise they form a balanced binary tree. This balanced binary tree can be implemented in several ways (splay, AVL, treaps etc.). So, if we have to add a node, we know what index the node will have, we’ll add the node in the binary tree and balance it. Similarily, removing a node and it’s subtree is setting updating every node to 0. Updating a subtree is similar to lazy decomposition we use in segment trees.
Author’s solution uses treaps to implement balanced binary trees.
ALTERNATE SOLUTION:
When you add a node to the tree you first just try to write all changes it gives (it gives +1 edge) to some list (let’s call it buffer), and don’t change anything in the tree structure. We should keep the size of the buffer small. Then we can split a query into two easier ones:
-
queries on the large tree (anything but buffer). This tree will not change after every single updating. We’ll rebuild it only when the size of the buffer is large by adding all the nodes from the buffer to it. And this will happen seldom. We can use some simple data structures like segment tree in order to manage it.
-
queries on the buffer. The size of the buffer is small (if it’s not, we’ll just rebuild the tree completely and clear the buffer), so we can check every single node from it, whether it’s suitable.
We should note that the buffer is practically a forest (a set of trees).
When the size of the buffer reaches 1666 we flush it and rebuild the tree. That means about 60 rebuilds, each is in O(N). And the queries are processed in O(size_of_the_buffer+log N) time. In practice it works within 1 sec.
See tester’s solution for details on this approach.