#P10752. 彩色树
彩色树
题目描述
一棵以 为根的树随时间生长。开始只有节点 ,随后按编号 的顺序逐个加入节点,每次用一条边将新节点与其父节点连接。
对任一时刻的整棵树,给每条边涂恰好一种颜色,颜色种类不限。染色合法当且仅当对每一种出现的颜色,其全部边连通且任一节点至多与两条该颜色的边相接。因此每种颜色的边形成一条简单路径。
对于一个合法染色,节点 的特征值 是从根到 的路径上不同边颜色的数量。整棵树的特征值为所有节点特征值的最大值。
每加入一个节点后,求当前整棵树在所有合法染色中的最小特征值。每个时刻独立选择染色。
输入格式
第一行一个正整数 。第 行()一个正整数 ,表示节点 的父节点。
输出格式
输出 行。第 行表示节点 加入后的最小特征值。
样例 1
3
1
1
0
1
1
样例 2
12
1
1
1
3
4
4
7
3
7
6
6
0
1
1
1
1
1
2
2
2
2
2
3
数据范围
- 的数据满足 。
- 的数据满足 。
- 另有 的数据保证整棵树的叶节点数不超过 。
- 所有数据满足 ,。