暂无测试数据。

蒜头君有一棵有根树，树的每一边都有边权，蒜头君想知道任意两点间最短距离之和为多少。另外，由于各种原因，蒜头君的树的边的边权会发生若干次改变，蒜头君想让你告诉他，每一次改变后，任意两点间最短距离之和为多少？

输入格式

第一行一个正整数 $n$，表示蒜头君的树上的结点个数。

接下来 $n-1$ 行，每行两个正整数 $x_i,y_i$，$x_i$ 表示 $i+1$ 号结点的父亲结点的编号，保证其父结点编号小于自己编号。$y_i$ 表示 $i+1$ 号结点的父亲结点与自己间边的距离。

接下来一行一个整数 $m$，表示树的边权发生改变的次数。

接下来 $m$ 行，每行两个正整数 $a,b$，表示将 $a$ 结点与其父亲结点之间的距离改为 $b$，保证 $a \ge 2$。

输出格式

先输出一个整数，表示对于原始的树任意两点间最短距离之和。

接下来 $m$ 行，每行输出一个整数，表示每一次改变后，任意两点间最短距离之和。

数据规模

4
1 1
1 1
1 1
1
2 2

9
12