P11766 「KFCOI Round #1」遥不可及

你未曾料到，烟火散尽，余烬渐冷，那一转身的轻易告别，却成了永远的诀别。 但是，你决意追寻她的身影，哪怕在这永无止境的重逢梦中。

$n$ 个地点构成了复杂的关系网。 但是现在这些地点复杂的路线关系被简化成为了**一棵树**。 你从每个点均出发一次，当你从点 $u$ 出发时，你会找到这个点能到达的所有最远点 $v_1,v_2,\cdots v_k$，并对每个 $v_i$，将 $u$ 到 $v_i$ 简单路径上的点权值加 $1$。 询问最终所有地点的权值总和。

无

无

样例一解释：  从 $1$ 出发，最远距离为 $3$，故到达 $5$ 和 $6$，各点权为 $[2,2,0,2,1,1]$； 从 $2$ 出发，最远距离为 $2$，故到达 $5$ 和 $6$，各点权为 $[2,4,0,4,2,2]$； 从 $3$ 出发，最远距离为 $3$，故到达 $5$ 和 $6$，各点权为 $[2,6,2,6,3,3]$； 从 $4$ 出发，最远距离为 $2$，故到达 $1$ 和 $3$，各点权为 $[3,8,3,8,3,3]$； 从 $5$ 出发，最远距离为 $3$，故到达 $1$ 和 $3$，各点权为 $[4,10,4,10,5,3]$； 从 $6$ 出发，最远距离为 $3$，故到达 $1$ 和 $3$，各点权为 $[5,12,5,12,5,5]$。 所以最终各点权和为 $44$。 （黄色为 $1$ 出发的路径；红色为 $2$；蓝色为 $3$；绿色为 $4$；青色为 $5$；紫色为 $6$。） *** **本题采用捆绑测试**。 - Subtask 1（20 points，1 s）：$1\le n \le 5000$。 - Subtask 2（40 points，1 s）：$1\le n \le 5\times 10^5$。 - Subtask 3（10 points，1 s）：树的形态为链。 - Subtask 4（10 points，2 s）：树的形态为菊花。 - Subtask 5（20 points，2 s）：无特殊限制。 对于所有测试数据，$1\le n\le 10^6$，$1\le w_i \le 10^9$，$1\le a_i \le n$，$1 \le b_i\le n$。 本题输入数据较大，请使用较快的读入方式和实现方式。请注意本题的栈空间。