g6-07521. 所有点对的带权距离和 未做

给定一棵以 $1$ 为根的有根树，共 $n$ 个结点，每条边有正整数长度。求所有无序点对之间的带权距离之和。

第一行一个整数 $n$。

接下来 $n-1$ 行，第 $i$ 行两个整数 $f_{i+1}$ 与 $w_{i+1}$：结点 $i+1$ 的父亲是 $f_{i+1}$，边 $(f_{i+1},i+1)$ 的长度是 $w_{i+1}$（保证 $f_{i+1}<i+1$）。

一行一个整数。

输入：

3
1 2
2 3

输出：

10

点对 $(1,2)$ 距离 $2$，$(2,3)$ 距离 $3$，$(1,3)$ 距离 $5$，和为 $2+3+5=10$。

• 对于 $30\%$ 的测试点，$1\le n\le 1000$；
• 对于 $60\%$ 的测试点，$1\le n\le 5000$；
• 对于全部测试点，$1\le n\le 2\times 10^4$，$1\le w\le 10^6$（答案可用 long long 表示）。