题目描述

蚂蚁一共修建了 $n$ 个蚂蚁巢。

首先，它们会修建 $0$ 号巢，然后，它们会依次修建 $1$ 到 $n-1$ 号巢。每次修建，都会从新巢连接且仅连接一条路线到某个旧巢。

求，两个点之间的最短距离是多少。

输入格式

首先输入一个整数 $n$，代表巢穴数量。当 $n=0$ 时，就意味着整个程序的输入结束。

接下来 $n-1$ 行，第 $i$ 行有 $2$ 个整数，代表与 $i$ 巢相连的巢 $a_i$，和之间的距离 $l_i$。

然后输入一个整数 $q$，代表问题数量。

接下来 $q$ 行，每行 $2$ 个整数 $x$，$y$，请输出 $x$ 巢和 $y$ 巢的最短路径距离。

输出格式

对于每一组测试数据输出 $1$ 行，这行有 $q$ 个整数表示答案。用一个空格间隔。

数据范围

$2\le n\le1\times10^5$

$0\le a_i\le i-1$

$1\le l_i\le1\times10^9$

$1\le q\le1\times10^5$

By @dengziyue