luogu#P9210. 蓬莱「凯风快晴 −富士火山−」

蓬莱「凯风快晴 −富士火山−」

题目背景

富士山,被当地人称为「神山」。这是一座休眠火山,最近一次喷发在 300300 年前。

向这样的山中投入不死之药,想必会直接喷发吧。如此便理解为什么月岩笠最终抗命。

题目描述

所谓的山,是一种上细下粗的结构。能不能在「树」里也找到这样的结构呢?

给定一个以 11 为根的大小为 nn 的有根树 TT。你需要找到满足宽度单调不减的导出子树中最大的一棵:

  • 记该导出子树为 T0T_0,共有 kk 层。
  • T0T_0 的根节点的深度为 11,计算出 T0T_0 中每个结点的深度 did_i。由此定义 T0T_0ii 层的宽度 wiw_i 为「所有深度为 ii 的节点的个数」。
  • 你需要使得 wiw_i 单调不减。即,w1w2wkw_1\le w_2\le \cdots \le w_k

记原树的点集和边集分别为 V,EV,E。导出子树是原树的一个连通块,它的点集 V0VV_0\subseteq V,边集 E0E_0EE 当中所有端点均在 V0V_0 内的边。导出子树的根,是组成它的所有节点中在原树内深度最浅的那一个TT 也可以被认为是自身的一棵导出子树。

如图所示,绿色的区域和橙色的区域分别是原树的导出子树。它们的根分别为 221313

注意:导出子树的定义略微不同于子树的定义。请不要将两者混淆。

请找到最大的符合条件的导出子树的大小。

输入格式

第一行一个正整数 nn,表示整棵树的大小。

接下来 n1n-1 行,每行两个整数 u,vu,v,描述树上的一条边。

输出格式

输出共一行一个整数,表示最大的符合条件的导出子树的大小。

10
1 2
2 3
3 4
3 5
2 6
6 7
1 8
8 9
8 10
9
17
1 2
2 3
3 4
4 5
4 6
3 7
7 8
7 9
7 10
2 11
2 12
1 13
13 14
14 15
14 16
13 17
16

提示

样例解释

如图所示,标灰的节点是两个样例中选出来的导出子树。

  • 样例 11 找到的导出子树,每一层的宽度分别为 {1,2,3,3}\{1,2,3,3\}
  • 样例 22 找到的导出子树,每一层的宽度分别为 {1,2,4,4,5}\{1,2,4,4,5\}

数据范围及约定

对于全部数据,1n5×1051\le n\le 5\times 10^5