트리 시행

$N=1$인 경우, 유일한 정점에 시행을 하면 적힌 수가 $1$이 된다. 따라서 답은 $1$이다.

이제 $N \ge 2$라고 하자.

먼저 어떤 정점에 적힌 최종 값이 $3$ 이상이 될 수 없음을 보이자. 어떤 정점 $v$가 시행을 통해 $3$ 이상이 되려면, 시행 직전에 $v$의 모든 인접 정점에 적힌 수가 적어도 $2$여야 한다. 그런데 $v$의 인접 정점 $u$가 $v$보다 먼저 시행되어 $2$ 이상이 되려면, 그 시행 직전에 $u$의 인접 정점인 $v$에 적힌 수가 적어도 $1$이어야 한다. 하지만 그때 $v$는 아직 시행되지 않았으므로 값이 $0$이다. 모순이다. 따라서 최종 값은 $0,1,2$ 중 하나뿐이다.

$N \ge 2$에서는 모든 정점에 적어도 $1$을 만들 수 있다. 예를 들어 아무 순서로나 모든 정점에 시행을 하면, 각 시행에서 인접 정점들의 값의 최솟값은 적어도 $0$이므로 시행한 정점의 값은 적어도 $1$이 된다.

이제 최종 값이 $2$인 정점들을 생각하자. 서로 인접한 두 정점이 모두 $2$가 될 수는 없다. 두 정점 $u,v$가 인접해 있고 둘 다 $2$가 된다고 하자. 둘 중 먼저 시행된 정점을 $u$라고 하면, $u$가 시행될 때 는 아직 시행되지 않았으므로 값이 이다. 따라서 는 가 될 수 없다. 모순이다.

따라서 값이 $2$인 정점들의 집합은 독립 집합이다.

반대로, 트리의 임의의 독립 집합 $S$에 대해 $S$의 정점들을 모두 $2$로 만들 수 있다. 먼저 $S$에 속하지 않는 모든 정점에 시행을 한다. 그러면 이 정점들의 값은 적어도 $1$이 된다. 그 다음 $S$의 정점들에 시행을 한다. $$는 독립 집합이므로 의 각 정점의 모든 인접 정점은 밖에 있고, 이미 값이 적어도 이다. 따라서 의 모든 정점은 가 된다.

그러므로 $N \ge 2$에서 최댓값은

$$N + \alpha$$

이다. 여기서 $\alpha$는 주어진 트리의 최대 독립 집합 크기이다.

트리의 최대 독립 집합은 동적 계획법으로 구할 수 있다. 트리를 $1$번 정점에 루트로 잡고 다음을 정의한다.

• $dp0[v]$: $v$를 독립 집합에 포함하지 않을 때, $v$의 서브트리에서 고를 수 있는 최대 정점 수
• $dp1[v]$: $v$를 독립 집합에 포함할 때, 의 서브트리에서 고를 수 있는 최대 정점 수

그러면 다음 점화식이 성립한다.

$$dp1[v] = 1 + \sum_{u \text{ child of } v} dp0[u]$$ $$dp0[v] = \sum_{u \text{ child of } v} \max(dp0[u], dp1[u])$$

최대 독립 집합의 크기는 $\max(dp0[1], dp1[1])$이고, 답은 $N+\max(dp0[1],dp1[1])$이다.

시간 복잡도는 $O(N)$이고, 메모리 사용량은 $O(N)$이다.