题目描述

给定一棵 $n$ 个点的树,点的标号为 ${1..n}$,每条边的长度都为 $1$,定义 $dis(a,b)$ 为 $a$ 与 $b$ 的最短距离。

对于 $a,b$,定义 ${p1..pk}$ 为所有满足 $dis(a,x)+dis(x,b)=dis(a,b)$ 的 $x$ 构成的集合,定义价值函数 $f$:

$$f(a,b)=\sum_{i=1}^{n} \min_{j=1}^{k}dis(i,p_j)*i$$

现在小 $\text A$ 有 $\text Q$ 次询问,每次给定 $a,b$,询问 $f(a,b)$。

输入

第一行一个正整数 $n$
第二行 $n−1$ 个正整数,第 $i$ 个正整数 $x$ 表示边 $(x,i+1)$,保证 $x<i+1$
第三行一个整数 $\text Q$
接下来 $\text Q$ 行,每行 $2$ 个正整数 $a,b$

数据范围

对于 $100%$ 的数据,有$1≤n,Q≤10^5$

思路

见代码。

代码