레이팅 미적용새해 축하를 위해 베시와 친구들은 빛나는 장식이 많이 달린 거대한 트리를 만들었다. 베시는 리모컨으로 장식을 켜고 끌 수 있다. 해가 뜨기 전에 베시는 장식들을 어떤 순서로(같은 장식을 여러 번 조작할 수도 있다) 조작하여, 트리가 모든 장식이 꺼진 상태로 시작하고 모든 장식이 꺼진 상태로 끝나게 하고 싶다. 베시는 켜진 장식들의 집합이 정확히 어떤 정점을 루트로 하는 서브트리일 때 트리가 멋져 보인다고 생각한다. 베시는 장식을 조작하는 순서가, 모든 서브트리에 대해 어느 시점에 켜진 장식들의 집합이 정확히 그 서브트리가 되는 성질을 만족하기를 원한다. 또한 장식을 켜고 끄는 데는 에너지가 들고, 베시는 에너지를 낭비하고 싶지 않으므로 수행할 수 있는 최소 조작 횟수를 구하고자 한다.
형식적으로, 정점에 \(1\dots N\) (\(2\le N\le 2\cdot 10^5\))의 번호가 붙고 \(1\)을 루트로 하는 트리가 주어진다. 각 정점은 처음에 비활성 상태이다. 한 번의 연산으로 정점 하나의 상태를 비활성에서 활성으로, 또는 그 반대로 바꿀 수 있다. 다음 두 조건을 모두 만족하는 연산 수열의 최소 길이를 출력한다.
- 정점 \(r\)을 루트로 하는 서브트리를, \(1\)에서 \(v\)까지의 경로(양 끝 포함)에 \(r\)이 놓이는 모든 정점 \(v\)로 이루어진 집합으로 정의한다. 트리의 \(N\)개의 서브트리 각각에 대해, 활성 정점들의 집합이 정확히 그 서브트리의 정점들이 되는 순간이 존재한다.
- 전체 연산 수열이 끝난 후 모든 정점은 비활성 상태이다.
출제자: Benjamin Qi
배점
- 입력 2-3: \(N \le 8\)
- 입력 4-9: \(N \le 40\)
- 입력 10-15: \(N \le 5000\)
- 입력 16-21: 추가 제약이 없다.
출제자: Benjamin Qi
첫째 줄에 \(N\)이 주어진다.
둘째 줄에 \(p_2 \dots p_N\) (\(1\le p_i
가능한 최소 길이를 출력한다.
3
1 16There are three subtrees, corresponding to \(\{1,2,3\}\), \(\{2\}\), and \(\{3\}\).
Here is one sequence of operations of the minimum possible length:
activate 2
(activated vertices form the subtree rooted at 2)
activate 1
activate 3
(activated vertices form the subtree rooted at 1)
deactivate 1
deactivate 2
(activated vertices form the subtree rooted at 3)
deactivate 3
riseoj 작성
출처 올림피아드 > USACO > 2022-2023 > January > Platinum