Triameter
Contest: Codeforces Round 813 (Div. 2)
Difficulty rating: 3200
Tags: binary search, data structures, dfs and similar, trees

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 < 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 < 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$$$.

Input format:
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 < 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.

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

Constraints:
Time limit: 4.5 s
Memory limit: 768.0 MB

Note:
The graph in the first test after adding the edges:

Example input:
4
1 2 2
4
1 2 3 4

Example output:
1 2 2 2

Example input:
7
1 2 3 4 2 1
7
2 1 3 7 5 6 4

Example output:
3 3 4 5 5 5 4

Editorial:
We will solve the problem independently $$$q$$$ times.
Let $$$f_v$$$ be the distance to the closest leaf from vertex $$$v$$$, can be found using a simple bfs with multiple start sources. Let $$$d'(u, v)$$$ be the distance in the resulting graph.
Then $$$d'(u, v) = \min(f_u + f_v + x, d(u, v))$$$. A short proof: we'll either go through an edge between two leaves or we won't. In the second case, the answer is clearly $$$d(u, v)$$$. In the first case, our objective is to get to a leaf as fast as possible, use an edge with weight $$$x$$$, and then move to the destination vertex.
We want to find the maximum possible value of $$$d'(u, v)$$$. As is pretty standard in tree problems, we can do small-to-large merging. Let's maintain $$$val[v][i] = $$$ the max value of $$$depth_u$$$ over all $$$u$$$ in the subtree of $$$v$$$ with $$$f_u = i$$$.
We have a variable $$$ans$$$, initially $$$ans = 0$$$. For some $$$lca$$$, we will first merge all the subtrees, and then add $$$lca$$$ to the merged $$$val[lca]$$$. We will also update $$$ans$$$ during this. The final answer will be $$$ans - 1$$$.
$$$ $$$
Merging two subtrees:
Suppose we are merging subtree $$$u$$$ into subtree $$$v$$$, $$$len(val[u]) \le len(val[v])$$$, with some current $$$lca$$$:
First of all, iterate $$$i$$$ from $$$0$$$ to $$$len(val[u]) - 1$$$. For every $$$i$$$, do this cycle: $$$j = max(0, ans - i - x)$$$; if $$$j < len(val[v])$$$ and $$$val[u][i] + val[v][j] - 2 \cdot depth_{lca} \ge ans$$$, then do $$$ans := ans + 1$$$ and continue, else break and continue to the next $$$i$$$.
Why does this work? Because all $$$val$$$ arrays are sorted in decreasing order. Why? Because for some vertex $$$v$$$ with $$$f_v > 0$$$, there is always a vertex $$$u$$$ in it's subtree with $$$depth_u > depth_v$$$.
After we are done with that, update $$$val[v][i] := \max(val[v][i], val[u][i])$$$ for every $$$i < len(val[u])$$$.
$$$ $$$
Adding $$$lca$$$ to the merged $$$val[lca]$$$:
When we are adding $$$lca$$$ to $$$val[lca]$$$, we update the answer in almost the same way, only we set $$$i$$$ to $$$f_{lca}$$$ and $$$val[u][i]$$$ to $$$depth_{lca}$$$. After that we either do $$$val[lca][i] := max(val[lca][i], depth_{lca})$$$ or if $$$len(val[lca]) = f_{lca}$$$, just append $$$depth_{lca}$$$ to the back of $$$val[lca]$$$.
$$$ $$$
Complexity:
This particular variant of small to large merging works in $$$\mathcal{O}(n)$$$ since when merging two structures of size $$$a$$$ and $$$b$$$, the new size is $$$\min(a, b)$$$. You can find the proof here.
Since we increase $$$ans$$$ at most $$$n$$$ times, and we can calculate $$$f_v$$$ for all vertices in $$$\mathcal{O}(n)$$$, the complexity is $$$\mathcal{O}(n)$$$ per query, so $$$\mathcal{O}(q \cdot n)$$$ for all queries.
Note that doing small-to-large merging once and updating $$$q$$$ answers simultaneously is much faster that doing small-to-large merging $$$q$$$ times. In the first case, you can even get away with using binary search to update the answer, in the second case you cannot.