#P10752. 彩色树

    ID: 9870 传统题 1000ms 256MiB 尝试: 2 已通过: 2 难度: 7 上传者: 标签>CF2300提高+/省选-树形 DP动态 DP势能分析

彩色树

题目描述

一棵以 11 为根的树随时间生长。开始只有节点 11,随后按编号 2,…,n2,\ldots,n 的顺序逐个加入节点,每次用一条边将新节点与其父节点连接。

对任一时刻的整棵树,给每条边涂恰好一种颜色,颜色种类不限。染色合法当且仅当对每一种出现的颜色,其全部边连通且任一节点至多与两条该颜色的边相接。因此每种颜色的边形成一条简单路径。

对于一个合法染色,节点 xx 的特征值 f(x)f(x) 是从根到 xx 的路径上不同边颜色的数量。整棵树的特征值为所有节点特征值的最大值。

每加入一个节点后,求当前整棵树在所有合法染色中的最小特征值。每个时刻独立选择染色。

输入格式

第一行一个正整数 nn。第 ii 行(2≤i≤n2\le i\le n)一个正整数 fif_i,表示节点 ii 的父节点。

输出格式

输出 nn 行。第 ii 行表示节点 1,…,i1,\ldots,i 加入后的最小特征值。

样例 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

数据范围

  • 10%10\% 的数据满足 n≤7n\le7。
  • 20%20\% 的数据满足 n≤103n\le10^3。
  • 另有 20%20\% 的数据保证整棵树的叶节点数不超过 1010。
  • 所有数据满足 1≤n≤1061\le n\le10^6,1≤fi<i1\le f_i<i。

原 PDF 题面及样例染色图