Problem H was intended to be solved using Priority Queue (similar to Dijkstra). An easier version of this problem is when the tree is a line graph, and the problem is to find $$$K$$$-th smallest sum of the elements in subarray. However, this solution will not work in the tree version because some of the pairs of nodes are counted two times.

One of the first important lemma is that the $$$K$$$-th smallest simple path of all unordered pair nodes is equivalent to the $$$2K$$$-th smallest simple path of all ordered pairs of nodes. This version will work, because now all pairs of nodes are counted exactly two times.

Now, in the ordered pairs version, we can use the solution of the line graph version. It is like multi-source Dijkstra, where each node might be the root of the tree. Unfortunately, this solution might have $$$O(N^2)$$$ elements pushed to the Priority Queue.

A solution is to sort the adjacency list by the weight, and introduce the next nodes one by one. One of the tester said that it is similar to how Left Child Right Sibling works. Now, there are $$$O(N)$$$ (or at most $$$2N$$$) elements in the Priority Queue, which will solve this problem in $$$O(K_{max} \log N)$$$.

There might be a solution using Binary Search the Answer (or Parallel Binary Search for the query version) and Centroid Decomposition with some pruning. We are unsure whether it will pass the time limit. As it is out of the competition syllabus, and it is also an overkill solution, we did not implement this solution. Until now, there has been no one who solve this problem with this approach.

We will always greedily try to take the leftmost $$$l$$$ where $$$A_l > 0$$$ and rightmost $$$r$$$ that still satisfies the condition of the operation. However, it's too slow to simulate the process naively.

Observation 1: Denote $$$op(l)$$$ as an operation where $$$l$$$ is the leftmost positive index. Assume that the right index $$$r$$$ is chosen optimally for $$$op(l)$$$. For every leftmost $$$l$$$ where $$$A_l > 0$$$, we will apply $$$op(l)$$$ at least $$$A_l$$$ times.

Observation 2: For any operation $$$op(l)$$$, if $$$A_l \leq A_{l+1}$$$, then the value of $$$A_{l+1}$$$ will decrease by $$$A_l$$$.

Observation 3: For any operation $$$op(l)$$$, if $$$A_l > A_{l+1}$$$, then after $$$A_{l+1}$$$ becomes $$$0$$$ in the process, $$$A_{l+1}$$$ will become $$$1$$$ after every 2 operations. Example case for clarity:

{5, 2, ...}
{4, 1, ...}
{3, 0, ...}
{2, 1, ...}
{1, 0, ...}
{0, 1, ...}

We can conclude that after $$$A_{l+1}$$$ becomes $$$0$$$, it will become $$$1$$$ for $$$\left\lceil {\frac{A_l - A_{l+1}} {2}} \right\rceil$$$ more times.

Let $$$f(i)$$$ be the number of times the value in index $$$i$$$ decrease. Notice that $$$f(i) \geq A_i$$$ and $$$f(i)$$$ is affected only by $$$f(i-1)$$$. Also, note that the value of $$$f(0)$$$ is $$$0$$$.

Let $$$ans$$$ be the total number of times we perform the operations. Then, for every $$$i < N$$$ it holds that:

• If $$$A_i \geq f(i-1)$$$, then $$$ans$$$ will increase by $$$A_i - f(i-1)$$$, and $$$f(i) = A_i$$$.
• If $$$A_i < f(i-1)$$$, then we increase $$$ans$$$ by $$$1$$$ if $$$(f(i-1) - A_i)$$$ is odd. This is because in this case, $$$A_i$$$ becomes $$$1$$$ and we need to apply 1 additional operation $$$op(i)$$$ to make sure that it becomes $$$0$$$. For this case, $$$f(i) = A_i + \left\lceil {\frac{f(i-1)-A_i} {2}} \right\rceil$$$.