CF1712F.Triameter

— What is my mission?

— To count graph diameters.

You and Your Submission

A tree is a connected undirected graph without cycles. A weighted tree has a weight assigned to each edge. The degree of a vertex is the number of edges connected to this vertex.

You are given a weighted tree with $n$ vertices, each edge has a weight of $1$. Let $L$ be the set of vertices with degree equal to $1$.

You have to answer $q$ independent queries. In the $i$-th query:

1. You are given a positive integer $x_i$.
2. For all $u,v \in L$ such that $u \lt v$, add edge $(u, v)$ with weight $x_i$ to the graph (initially the given tree).
3. Find the diameter of the resulting graph.

The diameter of a graph is equal to $\max\limits_{1 \le u \lt v \le n}{\operatorname{d}(u, v)}$, where $\operatorname{d}(u, v)$ is the length of the shortest path between vertex $u$ and vertex $v$.

— 我的任务是什么？
— 计算图的直径。

你与你的提交

树是一种无环的连通无向图。带权树为每条边赋予一个权重。顶点的度数是指与该顶点相连的边的数量。

给定一棵含 $n$ 个顶点的带权树，其中每条边的权重均为 $1$。令 $L$ 表示所有度数为 $1$ 的顶点构成的集合。

你需要回答 $q$ 个相互独立的查询。在第 $i$ 个查询中：

1. 给定一个正整数 $x_i$；
2. 对所有满足 $u,v \in L$ 且 $u \lt v$ 的顶点对，在图中（初始为给定的树）添加一条权重为 $x_i$ 的边 $(u, v)$；
3. 求所得图的直径。

图的直径定义为 $\max\limits_{1 \le u \lt v \le n}{\operatorname{d}(u, v)}$，其中 $\operatorname{d}(u, v)$ 表示顶点 $u$ 与顶点 $v$ 之间最短路径的长度。

The first line contains a single integer $n$ ($3 \le n \le 10^6$).

The second line contains $n - 1$ integers $p_2,p_3,\ldots,p_n$ ($1 \le p_i \lt i$) indicating that there is an edge between vertices $i$ and $p_i$. It is guaranteed that the given edges form a tree.

The third line contains a single integer $q$ ($1 \le q \le 10$).

The fourth line contains $q$ integers $x_1,x_2,\ldots,x_q$ ($1 \le x_i \le n$). All $x_i$ are distinct.

第一行包含一个整数 $n$（$3 \le n \le 10^6$）。

第二行包含 $n - 1$ 个整数 $p_2,p_3,\ldots,p_n$（$1 \le p_i \lt 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$ 互不相同。

Print $q$ integers in a single line — the answers to the queries.

在一行中输出 $q$ 个整数——各查询的答案。

The graph in the first test after adding the edges:

添加边后第一个测试用例的图：