Завдання зачарованих галявин#12982

Завдання зачарованих галявин (Розбір)

Author:

Roman Bilyi

Solved by:

First to solve:

Infinity

Let’s make a binary search to find the answer. Now we need to check whether we can add weights such that the diameter is .

Let’s call the middle point of the diameter . It means that the distance from point to any vertex is at most . And the existence of such point also means that diameter is – the distance between vertices and dist(a, b) \le dist(a, C) + dist(b, C) \le x/2 + x/2 = x.

The point should lie on an edge (considering vertices also lie on an edge). Let’s iterate an edge where the point lies. Let be the original length of this edge.

Property: We should only add weights to edges which connect edges to their corresponding parents. If we add some positive amount to an edge not connecting a leaf, we can add the same value to all edges connecting leaves in the subtree instead.

Now let’s find whether the point can lie on an edge . Let’s call mx_a – maximum distance from vertex to a leaf not using edge . Same for mx_b. Firstly, mx_a+len+mx_b should hold.

Let 0 \le y \le len be a distance from point to . If is even, should be integer. Otherwise, is integer + 0.5 (we can multiply all distances by 2, then we have a condition whether is even or odd).

The original distance from any leaf to can’t be more than , so mx_a+y \le x/2 and mx_b + len - y \le x / 2, so y \in [max(0, mx_b + len - x/2), min(len, x/2 - mx_a)]. If there is no possible solution, the edge doesn’t work.

Now let’s count how much weight we can add for a fixed and compare it with . Let da_1, da_2, \dots, da_k be the distances from to all leaves not using edge . Same for db_1, db_2, \dots, db_m. We can add \sum_{i=1}^k (x/2-y-da_i) + \sum_{i=1}^m (x/2 - (len-y) - db_i) = (x/2-y)\cdot k + (x/2-(len-y))\cdot m - \sum_{i=1}^k da_i - \sum_{i=1}^m db_i. It’s clear that the function is linear on so we can try minimal and maximal possible values of .

Now, how to compute all of this fast. It’s enough to compute values mx_a, cnt_a, sum_a, mx_b, cnt_b, sum_b for each edge.

Let cnt_a be the number of leaves reachable from not using edge .

Let sum_a be the sum of distances from to all leaves not using edge .

Then the formula become (x/2-y)\cdot cnt_a + (x/2-(len-y))\cdot cnt_b - sum_a - sum_b.

Now we only need to find all of those values for each edge. This is quite standard tree problem. We can compute all of those values for one edge and then recompute how the values change when we want to compute them for incident edges. This can be implemented in .

The complexity of the whole solution is O(n \cdot \log maxAnswer).