树是无环的连通无向图。加权树的每条边都分配有权重。顶点的度数是连接到该顶点的边的数量。
给你一棵带有 $$$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
注意
添加边后第一个测试中的图形: