CF379F New Year Tree

你是一名程序员，你有一棵新年树（不是传统的杉树）——它是一棵有四个顶点的树：有一个度为 $3$ 的顶点（编号为 $1$），它连接着三个叶子节点（它们的编号为 $2$ 到 $4$）。 在新年期间，程序员们通常会找乐子。你也决定找些乐子，通过向树上添加顶点来进行操作。每次添加操作如下： - 首先选择树上的某个叶子顶点，编号为 $v$。 - 设此时树上的顶点数为 $n$，那么会向树上添加两个顶点，编号分别为 $n+1$ 和 $n+2$，同时建立新边，把顶点 $v$ 分别与 $n+1$ 和 $n+2$ 相连。 你的任务不仅要模拟这种添加顶点的过程，还要在每次操作后输出当前树的直径。快来解决这个新年小问题吧！

第一行包含一个整数 $q$ $(1 \leq q \leq 5 \cdot 10^{5})$ —— 操作次数。接下来的 $q$ 行，每行包含一个整数 $v_i$ $(1 \leq v_i \leq n)$ —— 表示向顶点 $v_i$ 添加新的叶子的操作，其中 $n$ 表示当前树上的顶点总数。 保证所有给定操作都是合法的。

输出 $q$ 个整数，第 $i$ 个整数表示第 $i$ 次操作后当前树的直径。

由 ChatGPT 5 翻译