Since there is not much discussion going on I decided to make a post about my solution for the problem, be aware that I will go straight to the full point solution and won't discuss the partial score to save time for you. I'm quite busy lately so I don't have enough time to implement the code and submit to the online judge. Please give your opinion with your comments

P1

Putting ball with a value in the leaves, it will ascend to the root as much as possible and only stop when another ball blocking them, then harvest from them the dfs order of the vertices based on the value of the ball on each vertex, then discard all the balls and begin anew.

There is a limit on how many different value you can use (B) and number of them you harvest (K) that seems quite low compared to number of vertices (N ~ 1000) and leaves (M ~ 200) (B + K <= 44)

An unga bunga experiment you will urge to try is simply to choose a vertex, sending as much ball as possible with an unique value then move on to new vertex and new value until all the vertex has run out of space (*). Like this :

We can have the structure of full tree like this but it will cost B + K = M + 1 = 201 > 44

But we can apply (*) idea to reveal the structure of small subtree of T = 22 leaves with their ancestors and figuring out how other vertices connect to that structure progressively :

The way to update the structure progessively is the same as (*) but with one crucial observation to overcome the (201 > 44) wall : If we want to study how leaves T + 1, T + 2, ..., connect to the current structure of the tree of first T leaves by sending ball with unique values in those leaves, do we really need to represent the current structure of m leaves with m values by sending unique values in those leaves first like (*) ?

We will optimize how we represent the known structure using minimal values, so that there will be more remaining values and more leaves to update the structure each time :

Supposed the known structure of tree currently has P nodes with some leaves, we will assign to each node of the structure a value <= n(P) so that we can realize their position on the dfs array of that structure and send the unique values t > n(P) for each new leaf we want to add. Supposed the DFS array of the whole tree is a, and a' is a after removing all the values > n(P), a' is the dfs order of the P nodes tree, we can uniquely find out each position of a' correspond to which node of structure and how new nodes with values > n(P) connect to those vertices :

We see that we can deduce which position correspond to which vertices and how new vertices connect to them :

So how do we assign n(P) values for P vertices so that they are recognizable on their DFS array ? The hard part is that dfs algo of the problem statement order the child of a vertex with same value randomly so we don't know which one is which. The will be a strategy to assign values so that the position of each vertex is recognizable : Just need to assign value so that there are no scenarios where dfs array of two child of a same vertex, one array is prefix of another :

No dfs array of two child of a same vertex, one array is prefix of another, that condition can be satisfied if any path to any two leaf is different to each other. Since if u, v is the child of same vertex x and dfs array pu, pv of subtree of u, v based on assigned values, there will be a leaf u', v' that the value array on path u->u', v->v', are prefix of pu, pv. But the path from root -> x -> u -> u' and root -> x -> v -> v' is different, so those prefix is different, which mean pu, pv can't be a prefix to each other.

So we will find a way to assign the minimum values possible so that every path from root to any leaf is unique. We see to evaluate how new vertices connect to tree structure, if a vertex having a node that is not a leaf as its child, we can ignore all its leaves, or just keep 1 leaf if all its child are leaves. We can easily see that the worst case is that every 200 leaves has depth 2 from root, and each of them is adjacent to exactly one unique parent. That case for 200 leaves to have an unique path each we need 22 values because C(22, 2) > 200. So after building a tree structure of 22 leaves, each time we update the structure with x leaves from other 178 leaves, that will make a cost of K + B >= 21 + x + [178/x] >= 48 when choosing x = 13, a bit above the thresh hold. But we see that not every time we use 22 values since the number of leaf only reach 200 at the end, like for example at the beginning there are only 22 leaves we need only 8 values and can add 26 new leaves instead of 13. So we can fit below the threshold.

P2

This problem is more easy since our only job is just to study the structure instead of having to eureka billion of times to optimize marginally.

If there are odd number of statues, we put an additional fragile statue at 0. We assign each statue a color red or blue based on their x coordinate is positive or not, and the weight is the absolute number of their coordinate. The problem is equivalent to find a way to match statues into pair with minimal cost such that :

• If statues of weight a and b with different color matched, it costs |a — b|
• If statues of weight a and b with same color matched, it costs a + b
• No two fragile statues can be matched, except when they have the same weight and different colors.

Supposed the number of blue statue is at most number of red statue

The last condition can be ignored since we will always match two fragile statues with same weight and different colors for optimization eitherway, so delete any two fragile statue with different color and same weight from the problem. From now on we will can "red a" as a statue of color red with weight a, same with blue, also we will add the word "fragile" if it's a fragile statue and nothing otherwise. We can easily verify following condition in the optimized matching (we will assume the weight is strictly ordered by some tie-breaker between two equal weight) :

• There will be no match between 2 blue statue, since if so there will be a match between 2 red statues and we can exchange them for better cost. That means all blue statues will match to red statues (1)
• If a fragile red a matched with a red b, a fragile red c matched with blue d, then a <= c because we can exchange them for better cost otherwise. The same will hold if both red a and c are not fragile. That means we will pick some largest weight from fragile red and enough number of largest weight from normal red to match them all with blue. Other red balls left behind will match with each other. (2)
• If a fragile red c not matched with any blue ball then any normal red d with d <= c also not matched with no blue balls since we can exchange them to get better cost and reduce number of fragile statue to match later. That means if any normal red d matched with a blue c then every red b > d fragile or not, is also matched with a blue (3)
• The number of fragile blue put a threshold on minimum number of normal red to match with a blue, in turn put a threshold on maximum number of fragile red can be matched with a normal blue. The number of fragile red left behind also must not exceed number of normal red left behind, putting a threshold to minimum number of fragile red need to match with a blue. If those two threshold violate then it's impossible to match.
• If a normal red a is matched with a normal blue b, then for any red c matched with blue d, either both (c < a and d < b) or (c > a and d > b) else we can exchange them to get better cost. That means a normal red a is matched with a normal blue b then there are equal number of red statue weight > a and number of blue statue > b, and those set of statues is matched between each other. (4)

From (4) we see that if the red weight numbered $$$x_1 \lt x_2 \lt ... \lt x_r$$$ and blue weight $$$y_1 \lt y_2 \lt ... \lt y_b$$$ then in an optimal matching, if normal red $$$x_i$$$ matched with normal blue $$$y_j$$$ then $$$i = j$$$. We call $$$st(i) = true$$$ meaning $$$x_i$$$ and $$$y_i$$$ are both normal and is matched with each other. We also calculate $$$diff(i)$$$ = (number of normal statues — number of fragile statue among blue statues > $$$y_i$$$ and red statues > $$$x_i$$$) / 2.

Assume we numbered all the index $$$id_1 \lt id_2 \lt ... \lt id_t$$$ in an optimized matching so that $$$st(id_i) = true$$$. We see that $$$diff(id_i) = diff(id_{i+1}) - 1$$$ and every a red statue $$$x_i$$$ is matched with blue statue $$$y_j$$$ with different fragility with $$$id_i \lt i, j \lt id_{i + 1}$$$ (Same with $$$0 \lt i, j \lt id_1$$$) and every blue statue $$$y_i$$$ with $$$i \gt id_t$$$ is matched uniquely with a red state $$$x_j$$$ with $$$j \gt id_t$$$ with different fragility

More specifically, if we numbered all the fragile, normal red statues as $$$fx_1 \lt fx_2 \lt ... \lt fx_{Rf}$$$, $$$nx_1 \lt nx_2 \lt ... \lt nx_{Rn}$$$ and normal blue statues as $$$ny_1 \lt ny_2 \lt ... \lt ny_{Bn}$$$, fragile as $$$fy_1 \lt fy_2 \lt ... \lt fy_{Bf}$$$ then for every statues with 2 possible color and fragility among $$$x_{id_i}, ... x_{id_{i + 1}}$$$ and $$$y_{id_i}, ... y_{id_{i + 1}}$$$, there will exist a constant $$$d_1, d_2, d_3, d_4$$$ such that $$$fx_i$$$ matched with $$$ny_{i+d_1}$$$, same with $$$nx_i, fy_i, ny_i$$$ using $$$d_2, d_3, d_4$$$ as shifting index

So by using persistent segtree or some similar structure, we can record which shifting index $$$nx_i$$$ will contribute $$$+nx_i, -nx_i$$$ to the cost and similar to other type of color and fragility. Meaning that if we choose $$$i \lt j$$$ with $$$diff(i) = diff(j) - 1$$$ as the immediate adjacent index such that $$$st(i) = st(j) = true$$$, we can quickly calculate the cost to uniquely match all the statues of different color and fragility between index $$$i \lt j$$$ in $$$O(lgn(n))$$$. We can also calculate the change of cost when changing $$$j$$$ to another $$$j'$$$ such that $$$diff(j') = diff(j) = diff(i) + 1$$$ and $$$j' \gt i$$$, and that change won't be affected by $$$i$$$.

From that for each $$$i$$$ such that both $$$x_i, y_i$$$ not fragile, we find smallest $$$j = nxt1(i)$$$ such that $$$x_j, y_j$$$ also not fragile and $$$diff(j) = diff(i) + 1$$$, also smallest $$$j' = nxt2(i)$$$ such that $$$diff(j') = diff(i)$$$ and $$$x_{j'}, y_{j'}$$$ also not fragile. From that we define $$$dp(i)$$$ as the cost so far to match all the $$$x_j, y_t$$$ with $$$j, t \lt i$$$ and match non fragile $$$x_i$$$ with $$$y_i$$$. From the state $$$dp(i)$$$ we can translate to $$$dp(nxt1(i))$$$ when we decided to match normal statue of same index at $$$nxt1(i)$$$ next, or $$$dp(nxt2(i))$$$ when we decide to replace matching normal statue at index $$$i$$$ to $$$nxt2(i)$$$, with translation cost each time got calculated beforehand. So in the in we solved it in $$$O(nlg(n))$$$.

P3

https://codeforces.me/blog/entry/155911?#comment-1384991

I see that the problem this year is quite hard, even the winner got 2 out of 6 full solve. If there are enough upvote I might try to tackle D2 problem too.