Try solving the 3rd subtask

iterate on each bit from the highest bit to the lowest bit and increase the lower number by that bit. Then compare the two numbers in the end, if they are equal we are done. If they are not, then increase the smaller number by 1 and we are done. The proof of why this works is left to the reader.

Code: 270446214

Try doing what we did above by using something similar to divide and conquer.

Let solve(l, r) make everything from [l, r] equal, then we can do something like -

void solve(l, r):
  mid = (l + r) / 2;
  solve(mid + 1, r)
  solve(l, mid)
  subtask3(l, r)

Since everything from [l, mid] and [mid + 1, r] are the same, we can apply the subtask3 algorithm and make everything from l to r equal as well.

Note that this doesn't solve the problem. We need to optimise the number of add operations we use. This is left to the reader. Try grouping similar looking queries somehow.

Code: 270463943

Try solving subtask 4

Express the given number K as sum of powers of 2. Construct a solution for powers of 2 (previous subtask) and somehow find a way to add the number of ways up. This should solve the full problem.

Code: 270441721

The problem somehow seems to ask us to break the path between nodes X and Y into $$$O(log_{2}(N))$$$ segments, and somehow combine the answers using that.

We need to first figure out how to break the given path into $$$O(log_2(N))$$$ segments. One way is to use binary lifting! We can break the path from X to lca(X, Y) and the path from Y to lca(X, Y) into $$$O(log_2(N))$$$ segments each. We can pre-calculate some information for all such paths and somehow combine them to answer the query.

What information do we store for the paths? Let the path we store information for be $$$X \rightarrow Y$$$ (yes, its going to be directed. The answer from $$$X \rightarrow Y$$$ is not necessarily the same as the answer from $$$Y \rightarrow X$$$)

Let us store a 2x2 matrix. Lets call it Mat.

• $$$Mat[0][0] \rightarrow$$$ we cannot continue an already used high power at X, and we don't need to end with high power.
• $$$Mat[1][0] \rightarrow$$$ we can continue an already used high power to go to the next node from X, but we don't need to end with high power.
• $$$Mat[0][1] \rightarrow$$$ we cannot continue an already used high power at X, but we have to end with high power.
• $$$Mat[1][1] \rightarrow$$$ we can continue an already used high power to go to the next node at X, and we have to end with high power as well.

Combining two Mat's together is left to the reader, and so is the basecase.

However we use these precalculated Mat's to answer the queries using binary lifting.

Code:270456248

Note that the problem statement basically asks us not to have $$$3$$$ or more chosen nodes on any path. For this we can arbitrarily root the tree at any node, and do dp.

Let $$$dp[x][i]$$$ be the number of possible sets such that the maximum number of chosen nodes on a path from $$$x$$$ to a node in its subtree is $$$i$$$, for $$$0 \leq i \leq 2$$$

The transitions are left to the reader. The final answer will be $$$dp[root][1] + dp[root][2]$$$

Code: 270445208