Zygarde Gyeonggwak Forme

1. Reducing the tree to groups on the Core path

Let $V_1,V_2,\ldots,V_M$ be the vertices on the path from Core $A$ to Core $Z$, in order. Assign each vertex to its unique closest vertex on the Core path, and let $w_i$ be the number assigned to $V_i$. This group includes $V_i$ itself, so every $w_i$ is positive.

Only edges on the Core path may be deleted. Consequently, vertices in the same group always stay together, and each resulting component consists of a contiguous interval of groups. Conversely, any partition of the $M$ groups into exactly $K$ nonempty contiguous intervals can be obtained by deleting the $K-1$ edges between those intervals.

A pair of vertices in the same group contributes zero energy. For two different groups $i$ and $j$, there are $w_iw_j$ vertex pairs, each contributing $$. Therefore, the cost of making groups through one component is

$$C(l,r)=\sum_{l\le i<j\le r}w_iw_j(j-i).$$

To find the groups, root the original tree at $A$ and compute each vertex's parent together with a traversal order in which every parent precedes its children. Follow parents from $Z$ to recover the Core path. First assign group indices to all path vertices. Then traverse the other vertices in the recorded order and give each vertex its parent's group index. This takes $O(N)$ time.

2. Evaluating an interval cost in $O(1)$

Define the following prefix sums, with all values at index zero equal to zero:

$$W_i=\sum_{j=1}^{i}w_j,\qquad P_i=\sum_{j=1}^{i}j w_j,\qquad H_i=C(1,i).$$

When adding group $i$, only pairs between that group and earlier groups are new. Thus,

$$H_i=H_{i-1}+w_i(iW_{i-1}-P_{i-1}).$$

Set $t=l-1$. The difference $H_r-H_t$ includes both the cost within and the cost of pairs with one group in and the other in . Subtracting the latter gives

$$C(l,r)=H_r-H_t-W_t(P_r-P_t)+P_t(W_r-W_t).$$

After $O(M)$ preprocessing, this formula evaluates any interval cost in $O(1)$.

3. Dynamic programming

Let $DP_k[r]$ be the minimum cost of partitioning the first $r$ groups into exactly $k$ nonempty contiguous intervals. Enumerating the last interval $[l,r]$ gives

$$DP_k[r]=\min_{k\le l\le r}\{DP_{k-1}[l-1]+C(l,r)\}.$$

Initialize $DP_0[0]=0$ and all impossible states to infinity. The answer is $DP_K[M]$. Directly evaluating this recurrence takes time.

4. The Monge property and divide-and-conquer optimization

For $a\le b\le c\le d$, expanding the following difference yields

$$C(a,d)+C(b,c)-C(a,c)-C(b,d)=\sum_{i=a}^{b-1}\sum_{j=c+1}^{d}w_iw_j(j-i)\ge0.$$

Thus, the interval costs satisfy the Monge inequality. Adding $DP_{k-1}[l-1]$ to each candidate $l$ preserves this inequality. It follows that the optimal starting position of the last interval does not decrease as $r$ increases. Choosing the smallest starting position in a tie gives a consistent nondecreasing sequence of optimal positions.

To compute one $DP$ layer, first process the middle endpoint $mid$. If the possible optimal starting positions lie in $[L,R]$, inspect $l$ from $L$ through $$ and find an optimum . Recurse on the left half with candidate range , and on the right half with candidate range . For layer , start with endpoint range and candidate range . Ignore candidates whose previous-layer state is impossible.

The recursion has $O(\log M)$ levels, and the total number of inspected candidates at each level is $O(M)$. One layer therefore takes $O(M\log M)$ time.

5. Complexity and implementation details

The total time complexity is $O(N+KM\log M)$, and the space complexity is $O(N)$. Only the previous and current $DP$ layers need to be stored.

There are at most $N(N-1)/2$ vertex pairs, and each pair contributes at most $M-1$, so the total energy is less than $4\times10^{15}$. Also, and , so . The intermediate sums and differences in the cost formula fit in 64-bit integers as well. Use 64-bit integers for , , , , the values, and intermediate products. The original tree being unweighted does not make a 32-bit answer sufficient.

The tree can be a path with $N$ vertices. An iterative traversal avoids a stack overflow while building the groups. The divide-and-conquer $DP$ itself has only $O(\log M)$ recursion depth.