I've been trying to solve 1287D - Numbers on Tree using a randomized solution, but unfortunately, it keeps failing on test 21.

My solution is as follows: assign every leaf a random integer between $$$2001$$$ and $$$10^9 - 2001$$$ (even b/w $$$0$$$ and $$$10^9$$$ should work, but I chose these numbers just in case I get a random value too close to $$$0$$$ or $$$10^9$$$ in which case certain trees with $$$n = 2000$$$ might not be possible). Then, run a dfs starting from the root. If the current node in the dfs is a leaf, then we have already assigned it a value. Otherwise, call dfs on all it's children, and form a new multiset containing all the values the dfs of the children have returned. Do note that the dfs I have implemented returns a multiset containing the values of all nodes in it's subtree.

Then, based on the $$$c_{i}$$$ given in the input, I find a upper bound and lower bound in the multiset for the value to be assigned to the current node. I choose a random number between the bounds, add it to the multiset, and return. If at any point $$$c_{i}$$$ is greater than the size of the multiset, the answer is "NO".

This, I believe should work because the chance of choosing two values very close to each other is negligible (even with the bounds), and thus if a solution exists, this approach should always arrive at one.

However, test 21 of the problem seems to be some kind of test which forces my code to assign one value to more than one node even after all the randomness. I know this because my first solution used a set instead of a multiset, and the code was printing a "NO" for the testcase, while switching to a multiset simply led to a wrong answer being printed, in which the $$$c_{i}$$$ for some node in the tree the code printed had a difference of just one from what the $$$c_{i}$$$ was supposed to be (checker output told me this).

I've tried to construct a test case where my solution fails, to no avail. Also, test 21 is too big for me to make any sense out of it, so here goes.

• Can someone provide the construction of a test case where my solution fails (or the construction of test 21)?
• Is a randomized solution for this problem even possible?

My submission: 79126171