#PU1286. USACO 2023 January Contest, Platinum — Problem 3. Subtree Activation

    ID: 1541 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:jan23来源:usaco.orgscoring:equal_test_cases线段树

USACO 2023 January Contest, Platinum — Problem 3. Subtree Activation

USACO 2023 January Contest, Platinum — Problem 3. Subtree Activation

题目描述

For the New Year celebration, Bessie and her friends have constructed a giant tree with many glowing ornaments. Bessie has the ability to turn the ornaments on and off through remote control. Before the sun rises, she wants to toggle some of the ornaments in some order (possibly toggling an ornament more than once) such that the tree starts and ends with no ornaments on. Bessie thinks the tree looks cool if the set of activated ornaments is exactly a subtree rooted at some vertex. She wants the order of ornaments she toggles to satisfy the property that, for every subtree, at some point in time it was exactly the set of all turned on ornaments. Additionally, it takes energy to switch on and off ornaments, and Bessie does not want to waste energy, so she wants to find the minimum number of toggles she can perform. Formally, you have a tree with vertices labeled 1…N1\dots N (2≤N≤2⋅1052\le N\le 2\cdot 10^5) rooted at 11. Each vertex is initially inactive. In one operation, you can toggle the state of a single vertex from inactive to active or vice versa. Output the minimum possible length of a sequence of operations satisfying both of the following conditions: Define the subtree rooted at a vertex rr to consist of all vertices vv such that rr lies on the path from 11 to vv inclusive. For every one of the NN subtrees of the tree, there is a moment in time when the set of active vertices is precisely those in that subtree. Every vertex is inactive after the entire sequence of operations.

输入格式

The first line contains NN. The second line contains p2…pNp_2 \dots p_N (1≤pi<i1\le p_i<i), where pip_i denotes the parent of vertex ii in the tree.

输出格式

(见题面原文)

数据范围

Inputs 2-3: N≤8N \le 8 Inputs 4-9: N≤40N \le 40 Inputs 10-15: N≤5000N \le 5000 Inputs 16-21: No additional constraints. Problem credits: Benjamin Qi

样例

样例 1

3
1 1
6
There 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