## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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$. 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, add edge $\left(u,v\right)$ 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 $\underset{1\le u, where $\mathrm{d}\left(u,v\right)$ is the length of the shortest path

Solution Click Below:-  👉
👇👇👇👇👇

between vertex $u$ and vertex $v$.

Input

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},\dots ,{p}_{n}$ ($1\le {p}_{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},\dots ,{x}_{q}$ ($1\le {x}_{i}\le n$). All ${x}_{i}$ are distinct.

Output

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