PROBLEM LINK:Author: A Surya Kiran DIFFICULTY:MEDIUMHARD PREREQUISITES:Segment trees PROBLEM:Given a rooted tree, each of whose node is associated with an integer, "wealth". You have to perform two operations: EXPLANATION:Someone said in a previous editorial:
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. 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: Offline solution:Let's keep, for each query a time t, according to the sequence they arrived in input.
Now, we come to the part of finding the death times. Again, a very classic approach called binary search comes into play here :).
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: A node can be updated by simply updating decrement and healthofleastwealthynode 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:
Query and update operations are very standard. AUTHOR'S AND TESTER'S SOLUTIONS:To be updated soon. RELATED PROBLEMS:
This question is marked "community wiki".
asked 14 Apr '14, 23:45

DP to use hua hi nahi isme? Aise kaise chalega bhai... :D add Dp, maxflow, fourier transform.. you might wanna add van emde boas trees as well..cool shit that. Plus...codechef pe koi problem hard nhi hota..at max mediumhard hota hai..and jo hard hota hai wo actually me NPhard hota hai :D :D :D :D: answered 15 Apr '14, 15:39
3
@nitinj What is the point of posting such a useless comment on such a well written editorial. If you dont understand cool shit then dont comment on it.
(15 Apr '14, 16:32)
8
haha..dude ..i was just kidding..you took it too seriously https://www.youtube.com/watch?v=gonNutXijdI PS: editorial is great. No doubt in that
(15 Apr '14, 19:22)

It will be done on BFS run tree. We get logN * logN subarrays to update in the BFS run tree as the children of any node lie as a continuous subarray in the BFS run. So we build a Segment Tree on BFS run tree and reduce each update to logN steps. answered 18 Apr '14, 07:19

I suppose that tests were rather weak, my solution spend a lot of time (about 3 seconds) and memory (600 mb) on test which is generated inside the code. I used the first idea and thought my solution too slow but it passed tests in time. It seems there wasn't the test without any queries or something like that. My code. answered 15 Apr '14, 05:28

I had the same idea as the Online Solution here but I found it to be wrong because, the damage gets halved as we proceed down the subtree and hence the leasthealthy descendant may not be affected by the same value of damage as its ancestors (credits to @darkstar1122 for pointing this out). Thus only the information about the leasthealthy descendant is not of much use. Can you please clarify this? answered 15 Apr '14, 10:08

@notimesea: I decided to be not too strict on the constant factor of a solution. Basically I thought of allowing solutions with recursive implementation of some functions. But brute solutions are no where possible to get in the given time limit. And the cube cluster which codechef uses is faster than many personal computers and might be than yours also. answered 15 Apr '14, 11:50

@tinchy_stryder: I think you are confused between least healthy descendant of segment tree and least healthy descendant of original tree. answered 17 Apr '14, 15:55

The segment tree is built upon BFS or DFS run of tree? answered 17 Apr '14, 19:45
