CF1712F Triameter

——我的任务是什么？ ——计算图的直径。 你和你的提交 一棵树是一个无环连通无向图。加权树是指每条边都被赋予了一个权值的树。一个顶点的度数是与该顶点相连的边的数量。 给定一棵有 $n$ 个顶点的加权树，每条边的权值均为 $1$。令 $L$ 为所有度数等于 $1$ 的顶点的集合。 你需要回答 $q$ 个互不相关的询问。在第 $i$ 个询问中： 1. 给定一个正整数 $x_i$。 2. 对于所有 $u,v \in L$ 且 $u < v$，在图（初始为给定的树）中添加一条权值为 $x_i$ 的边 $(u, v)$。 3. 求添加边后所得图的直径。 图的直径定义为 $ \max\limits_{1 \le u < v \le n}{\operatorname{d}(u, v)} $，其中 $ \operatorname{d}(u, v) $ 表示顶点 $u$ 和顶点 $v$ 之间的最短路径长度。

第一行包含一个整数 $n$（$3 \le n \le 10^6$）。 第二行包含 $n-1$ 个整数 $p_2,p_3,\ldots,p_n$（$1 \le p_i < i$），表示存在一条连接顶点 $i$ 和 $p_i$ 的边。保证给定的边构成一棵树。 第三行包含一个整数 $q$（$1 \le q \le 10$）。 第四行包含 $q$ 个整数 $x_1,x_2,\ldots,x_q$（$1 \le x_i \le n$）。所有 $x_i$ 互不相同。

输出 $q$ 个整数，表示每个询问的答案，按顺序用空格分隔。

下图为第一个测试样例在添加边后的图示：  由 ChatGPT 4.1 翻译