Problem LinkAuthor: Igor Barenblat Tester: Misha Chorniy Editorialist: Bhuvnesh Jain DifficultyMEDIUMHARD PrerequisitesDynamic ConvexHull Trick, HeavyLight Decomposition ProblemYou are given a tree with $N$ nodes. $M$ speedsters travel on the tree. The $i^{th}$ speedster starts at time $t_i$ from vertex $u_i$ and travels towards $v_i$ at a constant speed of $s_i$. For every vertex, we need to find the first time, any speedster visited it. In case, it was not visited by any speedster, report the answer as 1. ExplanationFor simplicity, let us assume that the tree is rooted at node $1$ and the depth of all vertices from the root is calculated. The depth is basically the distance of the vertex from the root of the tree i.e. $1$. Let us first write the equation for time taken by speedster $i$ reach a vertex $x$. If the vertex doesn't lie on the path from $u_i$ to $v_i$ then it is not visited by speedster $i$, or the time taken is INFINITY (a large constant). For all the other vertices on the directed path from $u_i$ to $v_i$, the time taken is given by: $$\text{Time taken} = t_i + \frac{\text{Distance from vertex }u_i}{s_i}$$ $$\text{Distance between x and y} = \text{Depth[x]} + \text{Depth[y]}  2 * \text{Depth[lca(x, y)]}$$ where $lca(x, y)$ is the lowest common ancestor of vertices $x$ and $y$. We can now modify the equation for the time taken to reach any vertex on the path from $u_i$ to $v_i$ as follows: Let the lowest common ancestor of $u_i$ and $v_i$ be $lca$. Calculate the final time at which we reach vertex $v_i$. Let us denote this by $t_f$. We now split the path from $u_i$ to $v_i$ into 2 parts: one from $u_i$ to $lca$ and from $lca$ to $v_i$. NIte that these paths are directed. The image below shows how to calculate the time at any vertex $x$ and $y$ on the 2 different paths. From the above figure, for a node $x$ on path from $u_i$ to $lca$, the time to reach it is: $$\text{Time taken to reach x} = t_i + \frac{(Depth[u]  Depth[x])}{s_i} = \big(t_i + \frac{Depth[u]}{s_i}\big)  \frac{1}{s_i} * Depth[x]$$ Similarly, for a node $y$ on path from $lca$ to $v_i$, the time to reach it is: $$\text{Time taken to reach y} = t_f  \frac{(Depth[v]  Depth[y])}{s_i} = \big(t_f  \frac{Depth[v]}{s_i}\big)  \frac{1}{s_i} * Depth[y]$$ If we observe carefully, both the above equations look the form $Y = MX + C$, where the first bracket part is $C$, time to be calculated is $Y$, $\frac{1}{s_i}$ is the slope ($M$) and the depth of the node is $X$. The problem asks us to find minimum time at which every node is visited by any speedster, and the above equations clearly show that time to reach it only depends on the depth of the node and pair $(constant, slope)$ which is known beforehand for every speedster. Thus, this indicates the final solution will use the Dynamic convexhull trick (Dynamic variant as the slopes are not guaranteed to be in increasing/decreasing order). If you don't know about it or its use case, you can read it here So, let us first try to solve a simple version of the problem where the tree is a bamboo(a straight path). This basically rules out the tree of the problem and reduces it to updates and queries of the following form on an array:
We have range updates and point queries. So, we will use segment trees for the solution. In each node of the segment tree, we will keep the lines (represented by $(M, C)$) and for querying, we will just use the convexhull trick to evaluate the minimum at node efficiently. Below is the pseudocode for the segmenttree:
The time complexity of the above operations on segment tree is $O(\log{N} * \log{M})$ for both update and query. This is because each update and query will visit at most $O(\log{N})$ nodes and operation on every node (addition of a line or querying for minimum) is $O(\log{M})$. For a good reference code to the Dynamic convex hull, you can look up this. Back to the tree problem. We see that we can easily handle queries on an array and the queries on the tree as basically those on a path. Voila, we can simply use Heavy light Decomposition or any other data structure you are suitable with (Euler Path or Centroid Decomposition). Thus, we efficiently solve the problem. The overall timecomplexity of the above approach using heavylight decomposition will be $O({\log}^{2}{N} * \log{M})$ per update and query as it divides the path between the vertices $u$ and $v$ into $O(\log{N})$ path each of which is a straight path and can be solved using the segment tree mentioned above. You can look at the author's implementation for more details. Feel free to share your approach, if it was somewhat different. Time Complexity$O((N + M) * {\log}^{2}{N} * \log{M})$ Space Complexity$O(N + M)$ AUTHOR'S AND TESTER'S SOLUTIONS:Author's solution can be found here.
This question is marked "community wiki".
asked 11 Jun, 16:05

We can do this using basic union find and greedy If anyone wants to know my solution,tell me,i'll be happy to share it. Edit: My idea was to process vertices in increasing orders of smallest time of arrival of speedster. So basically i maintain a min priority queue of form (time,Starting Vertex,Destination Vertex,velocity) So for each speedster,put $(t_i,u_i,v_i,s_i)$ in priority queue Now at each step do the following: $1)$Remove the minimum time element from priority queue. $2)$lets say it is (t,u,v,s) So ans[u]=t and we can say that processed[u]=true $3)$Now go one step further along the path from u to v,(like for u>w>v,next vertex along path from u to v is w),let this vertex be w,so insert(t+dist(u,w)/s,w,v,s) in priority queue. $4)$Repeat Now if u see in step 3,there's no point in visiting vertex w if processed[w]=true, like lets say we have a chain like this, $a>b>c>d>e$ And processed[b]=processed[c]=true Also since a has been processed currently processed[a]=true And our current processed vertex is a,So for step $3)$ its not worth to go to b since its ans wont change,so it would better if we could directly jump to d,and insert d into priority queue. How do we do that? Lets define components,we basically group all vertices which are adjacent to each other and which have been processed into 1 group for the above case,we could say (a,b,c) belong to component no.1,d belongs to component No.2,e belongs to component No.3 So it becomes more like $(\textbf{a>b>c})_1>(d)_2>(e)_3$ (here bold indicates they are the processed vertices whose answer has been found and cannot be improved) Now how do we find that we have to go to d? U can use binary lifting sort of thing(Sorry if i am saying the name wrong,i just remember the method) lets say u have a vertex $u$,and vertex $v$ Lets root the tree at 1, we want to go to next nonprocessed along the path from u to v , first case ,u is below v(and the path is bamboo) So do this curr=u while True: $1)$iterate i from 20 to 1, See if 2^i th parent of curr is in same component as curr, if it is:
else
$2)$ if curr value not changed,it means that u are at the end of the component of u,so its parent is actually what you want eg: $(a>b>c)_1>(d)_2>(e)_3$ Imagine this upside down ,like a down ,e up ,wanna go from a to e So 2^2 parent of a is e(not in same component),so continue,2^1 parent of a is c(same component break) Now 2^1th parent of c is e(not same component so continue),2^0 th parent is d (not same component) So parent of c is what we wanted(which is d here) Second Case: u is above v(path is a bamboo) This too can be handled similarly Now if path doesnt form bamboo ,we can break it down like (u,lca(u,v)),(lca(u,v),v) My solution: https://www.codechef.com/viewsolution/18735059 answered 11 Jun, 17:16
Hey i am interested. Please do write an editorial on that. It took me a lot of time to code up 500+ lines and for sometime I did try thinking an easier alternative but didn't get any. Would be glad if you wrote and editorial :D
(11 Jun, 17:21)

I used Heavy light decomposition plus convex hull for each chain, splitting the chain in case cahin exceed a particular size. Kept getting WA on 1 file in last subtask. here answered 11 Jun, 17:56
I also kept getting WA for that particular case. Very curious as to why. Is there any way to get any insight in what actually went wrong? Is it at all possible to see that test case, @admin?
(11 Jun, 20:37)

This editorial is published twice https://discuss.codechef.com/questions/128890/arctreditorial and this page (https://discuss.codechef.com/questions/128889/arctreditorial) One can be deleted. answered 11 Jun, 16:23

My logic is almost the same instead I used sqrt dec. I don't know how but it did pass xD, though i had already thought of using segment trees in case it TLED. Glad it didn't :D. answered 11 Jun, 17:15

@taran__1407 @algmyr I too was getting the same verdict initially when I was using doubles in Convex Hull. On changing it to use longs I got AC. I had directly stored s_i and B and modified CHT to work with these long values instead). I suspect that WA on this case was due to floating point inaccuracy.(But I may be wrong as I also tried using the same code with long doubles in c++ but again got WA on this case). Can @admin provide us with this test case? Link to AC solution 18870510 answered 12 Jun, 20:44

@taran_1407 @algmyr I too was getting the same verdict initially when I was using doubles in Convex Hull. On changing it to use longs I got AC.(Here line $Y=MX+C$ has $M=\frac{1}{s_i}$ and $C=\frac{B}{s_i}$ where $B$ is a long value. This line can also be written as $\frac{1}{s_i}(X+B)$. Instead of calculating $\frac{1}{s_i}$ and $\frac{B}{s_i}$. I had directly stored $s_i$ and $B$ and modified CHT to work with these long values instead). I suspect that WA on this case was due to floating point inaccuracy.(But I may be wrong as I also tried using the same code with long doubles in c++ but again got WA on this case). Can @admin provide us with this test case?Link to AC solution 18870510 answered 12 Jun, 20:56

Author's and Tester's solutions, mentioned in the editorial give TLE on subtasks 2,3 and 4. Links answered 15 Jun, 16:12
You sure you exactly copied the code? Perhaps wrong solutions got linked. I will talk to @mgch and see what I can do.
(15 Jun, 16:30)
Thank you @likecs :)
(17 Jun, 18:23)
