题目描述

首先给出一棵以 $1$ 为根，$n$ 个结点的树，定义为「单位树」。

现有 $n$ 个结构与「单位树」完全相同的树，要将 $n$ 个树再用 $n-1$ 条边连接起来。

为方便叙述，用符号 $(a,b)$ 表示结点 $a$ 所代表树中，编号为 $b$ 的结点。

连接方式如下：

1. 将 $n$ 棵树按照「单位树」的结构摆放好。

2. 对于每个 $i(1<i\leq n)$，连接结点 $(i,1)$ 和 $(f_i,f_i)$。其中 $f_i$ 表示「单位树」中结点 $i$ 的父亲。

求将 $n$ 棵树连接后，整棵包含 $n^2$ 个结点的树中，树上两点简单路径所包含的 结点 个数的最大值。

输入格式

第一行输入一个正整数 $n$，表示「单位树」的结点数。

接下来输入 $n-1$ 行，每行两个正整数 $u,v$，表示「单位树」中的一条边。

输出格式

输出一行一个正整数，表示树上两点简单路径所包含的 结点 个数的最大值。

3
1 2
1 3

5

5
1 2
1 3
2 4
2 5

9

9
1 2
1 3
1 4
1 5
2 6
2 7
5 8
5 9

11

5
1 2
2 3
2 4
2 5

8

提示

样例说明

样例 #1

样例 #2 如下图，以 $(3,4)$ 和 $(4,4)$ 为两端的路径包含 $9$ 个结点，长度为 $9$。

样例 #3 如下图，取 $(6,6)$ 和 $(9,9)$，包含 $11$ 个结点。

事实上，任取两个最近公共祖先为 $1$ 的橙色结点，答案均为 $11$。

数据范围

本题采取捆绑测试。

子任务编号	分值	$n\le$	特殊性质
$1$	$10$		$\times$
$2$	$12$	$10^6$	$v=u+1$
$3$	$6$		$u=1$
$4$	$18$	$=2^k(k\in\mathbf{Z})$	$u=\left\lfloor\dfrac{v}{2}\right\rfloor$
$5$	$27$	$10^3$	树的形态随机
$6$		$10^6$	$\times$

对于 $100\%$ 的数据：$1\leq n\leq10^6$，结点编号介于 $1\sim n$ 之间。

本题可能略微卡常。

时限缩短为 1s，原因如下：

• 讨论区认为本题撞原，为防止所谓「加强版」的 $O(n\log n)$ 做法直接冲过本题，时限缩短。

• 最优解能跑进 200ms 以内。

• 由于出题人懒惰，懒得 $n\le10^6\rightarrow n\le10^7$ 只能通过缩短时限来卡掉所谓原题做法（实际上是错解）。