Max-plus tree

아래와 같이 루트가 있는 트리가 하나 주어진다. 아래 그림에서 가장 위에 있는 정점이 루트 정점, 아래에 있는 16개의 팔각형 형태 정점이 리프 정점이다.

리프 정점이 아닌 정점, 즉 14개의 내부 정점은 각각 max 정점 또는 plus 정점 중 하나로 지정되어 있다. max 정점은 원, plus 정점은 사각형, 리프 정점은 팔각형으로 표시한다.

각 정점의 값은 리프 정점에 배정된 값에 따라 결정된다. 리프 정점의 값은 리프 정점에 배정된 수이고, max 정점의 값은 자식 정점들의 값의 최댓값이며, plus 정점의 값은 자식 정점들의 값의 합이다.

당신은 16개의 수를 리프 정점에 배치해서 루트 정점의 값을 최대화해야 한다.

아래에서 직접 리프 정점에 수를 배치할 수 있다. 하단에 있는 수를 마우스로 드래그해서 리프 정점에 배치할 수 있다. 각 수는 최대 한 번씩 사용할 수 있다. 수를 리프 정점 바깥으로 이동시키면 수를 제거할 수 있다.

각 정점의 값은 정점 도형 안에 표시된다. 만약 리프 정점에 수가 배치되지 않았다면 그 정점의 값은 으로 취급한다.

모든 리프 정점에 수가 배치되지 않은 경우 점수를 받지 못함에 주의해야 한다.

채점 방식

모든 리프 정점에 수가 배치되었고 루트 정점의 값이 최대이면 전체 점수의 를 받는다.

문제 형식

인터랙티브

출처

• KOI 2023 1차대회 고등부 1교시 16번
• KOI 2023 1차대회 중등부 1교시 16번
• KOI 2023 1차대회 초등부 1교시 19번