Editorial

---

D

summary:

트리에서 1에서 출발하는 k개의 임의의 경로 위에 놓인 노드에 쓰여진 점수의 합의 최댓값을 구하는 문제이다.

같은 부모를 가진 어떤 노드 a,b 를 지나가는 경로의 개수의 차이는 1 이하이어야 한다.

solution:

$f(node,x)$를 node를 x번 지나가는 subtree의 점수의 합, $node$의 자식의 개수를 k라고 하자.

$node$에게 경로 $x$개가 할당되었기 때문에 자식 $x%k$명에게는 $x/k+1$개를, 나머지 자식에게는 $x/k$개를 할당할 수 있다.

그런데 누구에게 뭘 할당해 주어야 가장 나은 결과를 가져올지 모르기 때문에, 전부 $x/k$개, $x/k+1$개를 둘다 할당해 보고 차이가 큰 상위 $x%k$명에게 주려고 한다.

dp로 해결하면 된다.

opinion:

나도 자식에게 둘다 할당하는 경우는 생각 했고, 상위 $x%k$명에게 주는 생각까지 했으나, 차이를 기준으로 정렬할 생각을 하지 못했다.