Round-Robin Tree

Let $F_v(k)$ be the maximum score obtainable by sending $k$ balls into the subtree rooted at vertex $v$.

First handle vertices with exactly one child. If the only child of $v$ is $u$, every ball must move to $u$, so

$$F_v(k)=F_u(k).$$

Therefore, contracting every vertex with exactly one child does not change any distribution or score. A unary chain starting at the original root can be contracted in the same way. Every vertex in the contracted tree is now either a leaf or has at least two children.

For a leaf $v$, every ball stops there, hence

$$F_v(k)=kC_v.$$

Now consider a vertex $v$ with $d$ children. Write $k=qd+r$, where $0\le r<d$. Independently of the chosen order, every child receives balls, and exactly the first children receive one additional ball.

For a child $u$, the gain from receiving that additional ball is

$$D_u(q)=F_u(q+1)-F_u(q).$$

Any subset of $r$ children can be placed in the first $r$ positions. Therefore, the optimal choice is to select the $r$ largest values of $D_u(q)$, giving

$$F_v(k)=\sum_u F_u(q)+\text{the sum of the $r$ largest values among $D_u(q)$}.$$

For one fixed $q$, all states $k=qd,qd+1,\cdots,qd+d-1$ can be computed together. Sort all values in descending order and use their prefix sums.

Computing every state up to $X$ at every vertex is still too slow. Let $K_v$ be the maximum number of balls for which a state at $v$ can be required. For the contracted root, $K_{root}=X$. If has children, each child can receive at most

$$K_u=\left\lceil\frac{K_v}{d}\right\rceil$$

balls. Thus, only $F_u(0),F_u(1),\cdots,F_u(K_u)$ are needed.

To bound the number of states, define $E_v=K_v-1$. For every child $u$,

$$E_u=\left\lfloor\frac{E_v}{d}\right\rfloor.$$

Every internal vertex of the contracted tree has $d\ge2$, so a positive value of $E$ is at least halved on every edge. Moreover, the sum of $E$ over all children of one vertex does not exceed the parent's $E$. Hence, the sum of $E_v$ over one depth is at most , and positive values can occur on only depths. Vertices with contribute only a constant number of states each.

Therefore, the total number of DP states is

$$O(N+X\log X).$$

Sorting the marginal gains for each quotient group gives total time complexity

$$O((N+X\log X)\log N),$$

and the memory complexity is

$$O(N+X\log X).$$

Scores may be negative, and their absolute values can reach $2\cdot10^{14}$, so 64-bit integers are required.

Solution written by GPT5.6