PROBLEM LINK:Author: Misha Chorniy DIFFICULTY:Hard PREREQUISITES:HeavyLight Decomposition, Segment trees PROBLEM:Given is a tree of $N$ nodes and two constants $A$ and $B$. Each node in this tree has a value $C_v$ assosciated with it. We are further given two types of queries. The first query asks us to add a postitive constant $w$ to the all the nodes in the simple path from a node $u$ to another node $v$. The second query asks us to tell how many nodes exist such that $A*C_v + B \geq 0$. EXPLANATION:The problem clearly hints towards HeavyLight Decomposition. For those who don't know what Heavy Light Decomposition is, we recommend you check out Anudeep's Blog on it. To make the required updates and queries on the appropriate chains of the heavylight decomposition algorithm, we will keep a segment tree for each chain. Now, we need to know how to use the segment trees to perform the required range updates and range queries. For this, let us look at the constraints closely:
Let us consider the following four cases:
Now, we can rephrase the problem.
Now, we can formulate what all is required to be stored in the nodes of the segment tree in order to perform the updates and answer the queries. As our intuition tells us, the segment tree must process the updates using the lazy propagation technique. To achieve this, we need to store the following details per node:
A very crucial detail to be noted here is that $w$ is always a positive number. This means that once a leave is "dead", i.e., it has achieved a value of $\geq P$, it will remain dead for the rest of execution of the program. The query portion of the problem requires us to calculate the number of dead nodes on the path from $u$ to $v$. The last part of the algorithm is to see how to perform the lazy updates and how to efficiently count the number of dead leaves in the required range for the aforementioned segment tree. We give the pseudocodes for the update and query operations on the segment tree. For update, consider the pseudocode below:
For query, consider the pseudocode below:
An implementation detail to note in this question is that while updating/querying the path from node $u$ to node $v$, the LCA of the two may get updated/queried twice. Care needs to be taken for the same. Other implementation details for this method can be seen from Tester's/Editorialist's program. The proof of complexity is left to the reader as a simple yet interesting exercise. COMPLEXITY:$\mathcal{O}(N \log^2 N)$ per test case. ALTERNATE SOLUTIONSetter's solution uses squareroot bucketing of queries. Key observation: So if a * c[i][v] + b = 0 then a * c[i + 1][v] + b = 0, a[i + 2][v] + b = 0 ... a[n][v] + b = 0, so function f(i, v) = (a * c[i][v] + b = 0)  monotonic. $f(v) = 0 ... 0 1 ... 1$, we are interested in position of first 1  let it be ind[v]. Let's do queries in offline, firstly read them, after process. Divide queries by blocks of size K. After each block will memorize array of labels and recalc it. How to recalc? We know array for previous block, and some queries of first type in this block. In offline can do this queries with complexity O(N + K), add in offline and simple dfs. When we know array for previous block and current block, we are interested only in those elements for which changed value of function f. Let it be vector  V, for each element of vector V  v, go through this block of queries and find ind[v]. For each vertex we can find ind[v] in time O(K), so total complexity: $\mathcal{O}(N \sqrt{N})$. SAMPLE SOLUTIONS:
This question is marked "community wiki".
asked 20 Dec '15, 01:35

@pushkarmishra : your's , Author n tester sample soln are access denied. can u please give the link of your sample solution.And how node.number_alive are updated ? answered 11 Jan '16, 20:18

Have been trying this problem for a while now and keep getting WA. I have tested my solution against the one provided by you in the link above for 30,000+ random test cases of all kinds of trees (linear chain tree, random tree, max test case, lots of tiny tests etc) and it has passed all of them :/ Have tried all sorts of assertions and shenanigans to get some kind of feedback from the system about my answer as well. This is my solution http://ideone.com/RCaqyR Was wondering if you could provide me with the test cases or could tell me the flaw in my program. Thanks :)
link
This answer is marked "community wiki".
answered 20 Feb '16, 21:24
