Asm.Def的基本算法

【题目描述】

“有句美国俗语说，如果走起来像鸭子，叫起来像鸭子，那就是一只鸭子。”斯科特·华莱士看着$Asm.Def$面前屏幕上滚动的绿色字符，若有所思地说。

“什么意思？”

“你的数据。看上去是一棵树。”

“按照保密条令，我什么也不说这是最好的——但见你这么热情，一句话不说也不好。”$Asm.Def$停下手中的快速数论变换，“确实是树。”

“然后你怎么算出来目标的位置？”

“都需要按照基本算法，按照图论的那一套理论，去产生。听说过$LCA$吗？不是那个印度飞机，我是说最近公共祖先……”

$Asm.Def$通过分析无线电信号得到了一棵有$n$个节点，以$1$为根的树。除$1$之外，节点$i$的父亲是$p_i$。节点带有权值，节点$i$的权值是$w_i$。

我们定义某点的祖先为从根到它路径上的所有点（包括它本身），而两个节点$a$、$b$的最近公共祖先是某个点$p$，使得$p$同时是$a$、$b$的祖先，而且$p$离根最远。

$Asm.Def$想要求出:

$\sum\limits_{i=1}^n \sum\limits_{j=1}^n W_i * W_j * W_{LCA(i,j)}$

其中$LCA(i,j)$是$i$、$j$的最近公共祖先，他认为这个值至关重要。由于这个值可能很大，$Asm.Def$只需要知道它模$1,000,000,007$（即$10^9+7$）的结果。

【输入格式】

第$1$行两个整数：$n$和$w_1$.

第$2$行到第$n$行，第$i$行有两个整数$p_i$和$w_i$。

【输出格式】

一行一个整数，即答案模$1,000,000,007$的值。

【样例输入】

2 2
1 1

【样例输出】

17

【提示】

$1×1×1+1×2×2+2×1×2+2×2×2=17$。

对于$30$%的数据，$n<=100，w_i<=10$。

对于$60$%的数据，$n<=1000，w_i<=1000$.

对于$100$%的数据，$1<=n<=10^5，0<=w_i<=10^9，1<=p_i<i$.

【来源】

“$Asm.Def$战记之太平洋”杯