← 返回题目列表

Codeforces · 1712/F

F. 三步仪

中文机器翻译题面 查看原题

树是无环的连通无向图。加权树的每条边都分配有权重。顶点的度数是连接到该顶点的边的数量。

给你一棵带有 $$$n$$$ 个顶点的加权树,每条边的权重为 $$$1$$$。设 $$$L$$$ 为度数等于 $$$1$$$ 的顶点集。

您必须回答 $$$q$$$ 独立查询。在第 $$$i$$$ 查询中:

1. 给你一个正整数$$$x_i$$$。
2. 对于 L$$$ 中的所有 $$$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$$$ 整数 — 查询的答案。

示例

输入 #1

4
1 2 2
4
1 2 3 4

输出 #1

1 2 2 2

输入 #2

7
1 2 3 4 2 1
7
2 1 3 7 5 6 4

输出 #2

3 3 4 5 5 5 4

输入 #3

3
1 2
1
1

输出 #3

1

注意

添加边后第一个测试中的图形: