[Solution] Triameter Codeforces Solution

[Solution] Triameter Codeforces Solution | Solution Codeforces

F. Triameter

time limit per test

4.5 seconds

memory limit per test

768 megabytes

input

standard input

output

standard output

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$1$. Let 𝐿$L$ be the set of vertices with degree equal to 1$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 max1≤𝑢<𝑣≤𝑛d(𝑢,𝑣)$\underset{1\le u<v\le n}{max}\mathrm{d}(u,v)$, where d(𝑢,𝑣)$\mathrm{d}(u,v)$ is the length of the shortest path

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 between vertex 𝑢$u$ and vertex 𝑣$v$.

Input

The first line contains a single integer 𝑛$n$ (3≤𝑛≤106$3\le n\le {10}^6$).

The second line contains 𝑛−1$n-1$ integers 𝑝2,𝑝3,…,𝑝𝑛$p_2,p_3,\dots ,p_n$ (1≤𝑝𝑖<𝑖$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≤𝑞≤10$1\le q\le 10$).

The fourth line contains 𝑞$q$ integers 𝑥1,𝑥2,…,𝑥𝑞$x_1,x_2,\dots ,x_q$ (1≤𝑥𝑖≤𝑛$1\le x_i\le n$). All 𝑥𝑖$x_i$ are distinct.

Output

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