PROBLEM LINK:

Practice
Contest

Author: A Surya Kiran
Tester: Shiplu Hawlader and Mahbubul Hasan
Editorialist: Lalit Kundu

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

Segment trees
BIT
DFS, BFS, Graphs

PROBLEM:

Given a rooted tree, each of whose node is associated with an integer, "wealth". You have to perform two operations:
* A,X ie. decrease "wealth" of all nodes B by, by X/2^d where d is distance between the node B and node A.
* Report number of descendants of a given node with non-positive "wealth" (further referred to as "dead" in editorial).

EXPLANATION:

Someone said in a previous editorial:

Trees are hard to think about. In many tree problems involving data structures, the first step is to form one(or several) linear structures, and phrase the problem in terms of these linear structures.

Here, if we do a BFS on the tree, all the immediate children of node are numbered consecutively. We can use this to our advantage, but a bomb dropped on a node A effects all nodes in the tree according to distance.
Intuition here would be define a new kind of bomb, say NBomb, which when dropped on node A effects all it's descedants according to the distance from node. Also, it should effects A's parent by X/2. But now, since A is immediate child of it's parent, it would be effected more than X. To normalise that, we drop a NBomb of -(X/4) on A.
So, we drop two NBombs on A, one whose power is X and the other whose power is -(X/4) and an NBomb of power (X/2) on parent of A.
For dropping a NBomb on A, at every step we go down the tree level by level and damage cities in every level until 2^d>X. How we do this is by keeping for each node the leftest and rightest nodes. So, if we update an interval [i,j] by T, we will update [leftest[i],rightest[j]] by T/2.

So each query of type one is broken down in logX*logX queries, where each query is updating in a subarray(in the array we build after performing a BFS on the tree).

Now, we can have two approaches to solve this problem:
i.) Offline solution
ii.) Online solution

Offline solution:

Let's keep, for each query a time t, according to the sequence they arrived in input.
The approach here is to find for each node, the time of death. Once we get time of death for each node, it's very simple to find the answer for query two. Let's just say, we have times of death for now.
We have query of type two, which asks for number of descendants of a node which are dead at time=t. Again, we map the tree to an array using DFS, where all descendants of a node lie in one subarray.
We traverse over time now and keep on marking in BIT those indexes which have died before that time. For a query of type two, we just have to print the number of marked elements in L to R inclusive.

set BIT <- 0   
for t=1 to Q:    
    for each node whose death time=t:   
         update(BIT,t,1)   
    for query of type-two at time=t   
         print read(BIT,R)-read(BIT,L-1)

Now, we come to the part of finding the death times. Again, a very classic approach called binary search comes into play here :).
For each node, I suppose that it died at time T. If it is dead at time T, it will be dead at time T+1 too. So, we can use binary search here, as it's a non increasing function.
So:

def get_death_time(node n):    
     if sum of decrement queries till Q < wealth[n]:      
       return INF   // didn't die till the end        
     low=1     
     high=Q    
     while(low < high)    
      t1 = (low + high)/2   
      if (wealth[n] <= getDecSum(t1))   //get sum of all decrement queries performed upto time t1 that effect node n
           high = t1   // node is dead at time t1   
      else   
           low = t1+1  // node is not dead at t1    
     return low

However, we still have to get hold of all operations that effect node n, and use them to construct our BIT. To do this efficiently, we can use the fact that all operations affect some continuous subarray of our array. If Chef A comes immediately after chef B on the array, the operations that effect chef A are going to be almost same as those that effect chef B. Only those operations whose range either ends at B, or begins at A have to be taken care of. Rest of the operations are going to be common. Here is a pseudo code showing how to accomplish this:

set BIT <- 0
for i=1 to N:   
     for each query of type1 ie. (dec,i,r) at time t:  \\ that is, l=i   
          update(BIT,t,dec)   
     death[i]=get_death_time(i)   
     // This part can also be calculated in O(1) by reading    
     // the actual frequency at a position in BIT. See topcoder tutorial.   
     for each query of type1 ie. (dec,l,i) at time t:  \\ that is, r=i   
          update(BIT,t,-dec)

Hence, we get death times of all nodes.

Online solution:

In, online solution, you update all subarrays that need to be updated due to query of type1. And, then it figures out all the dead nodes in the tree. So, the only difference here, is that while updating the damages, we find the nodes which have died and update them in our BIT. And similar to offline solution, we can print using BIT, the number of dead nodes at any time.

I don't think I can do any better than this editorial by Utkarsh Lath. So, I am taking the segment tree lazy propagation part from this editorial.

To efficiently decrease all values in a subarray, we would need lazy propagation. Also, to efficiently determine nodes who have died due to an update, each node(of our segment tree) should store the descendant leaf of minimum health(this leaf will be the first to die if all descendants are poisoned). The overall structure of a node of our segtree is:
struct node { int health-of-least-wealthy-node, decrement , alive-count; // Actual health of a leaf(in segtree) can obtained by subtracting decrement value of all its ancestors(in segtree). // This is called lazy propagation. }

A node can be updated by simply updating decrement and health-of-least-wealthy-node parameters. decrement would need to be propagated down before updating any node. After performing a normal update, the following function can be used to remove dead chefs:

function remove-dead-nodes(int root) if tree[root].health-of-least-wealthy-node > 0 return // no dead node below me if is-leaf(root) set alive-count of root to 0, health-of-least-wealthy-node to infinity else propagate the value of decrement to both children, set decrement of root to 0 remove-dead-nodes(root * 2); // some dead chef exists and needs to be removed remove-dead-nodes(root * 2+1); // so check both children update health-of-least-wealthy-node and alive-count parameters of root

Query and update operations are very standard.

AUTHOR'S AND TESTER'S SOLUTIONS:

To be updated soon.

RELATED PROBLEMS:

MLCHEF
DQUERY
GSS4
CTRICK