Author: lllyouo
Date: 20250325
tag: 树的直径、最近公共祖先
link: 暂无

问题描述

科学家在观测一棵大树，这棵树在不断地生长，科学家给这棵树的每个节点编了号。开始的时候，这棵树很小只有 $4$ 个节点，一号点为根，其他三个节点挂在上面。

在接下来的 $M$ 次观察中，科学家每次都能看见这棵树从叶子处长出新的两个节点来。如果当前这棵树有 $N$ 个节点，那么这棵树的新的两个节点的编号分别为 $N+1$，$N+2$。科学家记录下了这棵树生长的过程，需要你帮着计算这棵树实时的直径。树的直径就是这棵树最远的两个节点的距离。

样例

样例输入：

第一行一个整数 $m$，接下来 $m$ 行，每行一个整数 $x$ 代表这棵树编号为 $x$ 的节点下面又长出了两个叶节点。

5
2
3
4
8
5

样例输出：

3
4
4
5
6

分析

维护直径的两个端点 $p$ 和 $q$，对于新增加的两个节点 $x,y$，由于其地位相同，任选一个即可，之后根据直径的性质（如果在一个节点上新增加一个叶节点，那么最多会改变直径的一个端点）计算 $dis(p,x)$ 和 $dis(q,x)$，如果比原来的直径长，则记录更新即可。

参考代码

暂无