# EXPLANATION
For the first subtask, the size of the tree is small enough so you can implement algorithm straightforward.
For the full solution, first of all, we need to merge every node v with his child if v has 1 child. After that, since we do every work on the leaf and every node other than leaf has degree >1, if we calculate path from leaves to nodes the path value, for particular leaf we only need to consider log(10^6) parents of the leaf.
Now after we calculated for every leaf v every possible value of the path. We can solve for all queries in âofflineâ by eratosthenes, we iterate over every possible path from v to leaf which is divisor of w
divison factor means number of division that a node can perform from itself to any reachable leaf node.
if the number of given tasks modulo divison factor of given node is zero then all the tasks get executed so answer is 0
else in other case i calculated maximum possible tasks that can be solved and this will be equal to the gcd of division factor of node v and the number of tasks w and if we divide the number of tasks by gcd then we will have non executed tasks.
An interesting point is that factorization doesnât seem necessary at all for w during queries. One of my friends used the fact that the number of distinct product of degrees till a leaf must be small, so if we keep track of the count in a map for each node, the construction is is still O(n * log^2(n)) but we can naively answer queries by just checking if each value in the map divides it.
While the proof for this is likely trickier than that for the editorial idea, at least intuitively it seems true, and in practice it appears to run faster than my solution which solves the problem in a similar manner to the editorial in O(n * log^2 n + q * (\sqrt{W} + divisors(W) * log(n)).
So for each query we would traverse all the leaves that would have some contribution ( the product of sizes of the parents of the leave is less than 10^6). I was able to generate some cases where the number of distinct leaves which have some contibution came around 600 to the root node ( each node has 2, 3, 4, 5, 6 or 7 children). So was Q * 700 the inteded solution ? I just felt the test cases were a bit weak. Upd: That 700 hundred comes from the fact that the number of distinct leaves cannot be more than sqrt(N). But how does compressing the tree help ( removing the nodes that have only one child ), for me it just looks like a random heuristic that worked.
I am sure I am missing something and it would be helpful if someone points it out.
I found a slightly different solution that worked. As in the editorial I merged nodes with only 1 child, but then used simple recursion. I however speeded this up in two ways:
I pre-calculated a âperfectâ value for each node, which is the minimum non-zero value required for a node to perform all tasks assigned to it. If the number of tasks is any multiple of this then all tasks will be completed
I cached the results for every node in a map (Python dictionary).
Neither of these is guaranteed to make a difference, however, between them they got me full points.
In your function âlostâ you are passing a vector g, what this is doing is you are actually passing a copy of vector g every time and this is time consuming for large vectors . So you should pass by reference like this:- ll lost(vector<vector<ll>> &g, ll u, ll k)
your solution with just the â&â changed-CodeChef: Practical coding for everyone
Only the last 3 task tle.
Having found the children of each node I created a Disjoint Union (see Disjoint union - Wikipedia). If a node only had one child I placed it and its child in the same set set. This gave me sets of nodes with each set containing precisely one node with either 0 or more than 1 child. I could then treat each of these sets as a single node for the recursion.
