Hirak Rajar Desh

Let’s assume we know all the leadership values of the captured ones, now how would you place them in prison cells?

Observation: If multiple people have the same leadership value, we can put them in the same cell as it won’t affect the probability.

So, we only need distinct leadership values. After finding the values, we can do a binary search on the range of values (Max-Min) that we’re going to put in a cell. Let’s say the range is $x$, if we need more than $k$ cells with range $= x$, then we need to increase the range, otherwise, we try decreasing it.

Now, how do we get the distinct leadership values? Let’s try to find the frequency of each leadership value in that path.

Take an arbitrary root, and for each node, we calculate the frequency of all leadership values which are in a simple path from the root to that node. This can be done using a simple dfs with prefix sum(parent sum in this case) in $O(n*k)$ complexity. Now for finding the frequency of a leadership value l in a simple path from $u$ to $v$, we can do $freq[l]=freq[u][l]+freq[v][l]-2*freq[LCA(u,v)][l]$. Here, $LCA(u, v)$ represents the Lowest Common Ancestor of $u$ and $v$ in that tree.

Complexity: $O(n*log(n)+n*k+q*log(k))$