UVA12238 Ants Colony

蚂蚁一共修建了 $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](/user/387840)