Round-Robin Tree

정점 $v$를 루트로 하는 서브트리에 공을 $k$개 넣었을 때 얻을 수 있는 최댓값을 $F_v(k)$라 하자.

먼저 자식이 하나인 정점을 처리한다. 정점 $v$의 자식이 $u$ 하나뿐이라면 모든 공이 반드시 $u$로 이동하므로

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

이다. 따라서 자식이 하나인 정점들을 모두 압축해도 공의 분배와 점수는 변하지 않는다. 루트부터 자식이 하나인 경로가 이어지는 경우에도 같은 방식으로 압축한다. 압축된 트리의 모든 정점은 리프이거나 자식이 적어도 두 개이다.

리프 $v$에서는 모든 공이 그 리프에서 멈추므로

$$F_v(k)=kC_v$$

이다.

이제 자식이 $d$개인 정점 $v$를 생각하자. $k=qd+r$이고 $0\le r<d$라 하자. 자식 순서와 관계없이 모든 자식은 공을 개씩 받고, 순서의 앞 개 자식만 공을 하나 더 받는다.

자식 $u$가 추가 공을 하나 받을 때의 이득은

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

이다. 앞 $r$개 위치에는 어떤 $r$개의 자식도 놓을 수 있으므로, $D_u(q)$가 큰 자식 $r$개를 고르는 것이 최적이다. 따라서

$$F_v(k)=\sum_{u}F_u(q)+\text{$D_u(q)$ 중 큰 값 $r$개의 합}$$

을 얻는다.

같은 $q$에 대해 $k=qd,qd+1,\cdots,qd+d-1$을 한꺼번에 계산할 수 있다. 모든 자식의 를 내림차순으로 정렬하고 누적합을 만들면 이 구간의 상태를 모두 계산할 수 있다.

모든 정점에서 $0$부터 $X$까지 계산하면 여전히 너무 느리다. 정점 $v$에 실제로 필요할 수 있는 공 개수의 최댓값을 $K_v$라 하자. 압축된 루트에서는 $K_{root}=X$이다. 자식 수가 인 정점 의 자식 는 최대

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

개의 공만 받을 수 있다. 따라서 $F_u(0),F_u(1),\cdots,F_u(K_u)$만 계산하면 충분하다.

상태 수를 증명하자. $E_v=K_v-1$이라 두면 자식 $u$에 대해

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

이다. 압축된 트리에서는 $d\ge2$이므로 양수인 $E_v$는 한 단계 내려갈 때마다 적어도 절반이 된다. 또한 한 정점의 자식들에 대한 $E$의 합은 부모의 $E$를 넘지 않는다. 따라서 같은 깊이의 모든 $$의 합은 이하이고, 양수인 가 존재할 수 있는 깊이는 개뿐이다. 인 정점은 정점마다 상수 개의 상태만 추가한다.

결과적으로 전체 DP 상태 수는

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

이다. 각 $q$마다 자식들의 이득을 정렬하므로 전체 시간 복잡도는

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

이고, 메모리 복잡도는

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

이다.

점수는 음수일 수 있고 절댓값이 $2\cdot10^{14}$까지 커질 수 있으므로 64비트 정수를 사용해야 한다.

Solution written by GPT5.6