Extra
Time
LCA的统计 Time:1s Memory:50M AC:0% Submit:2

描述

    萌蛋有一棵n个节点的有根树,其根节点为1。除此之外,节点i的父节点为p[i]。每个点上都有一个权值,节点i的权值是w[i]。
萌蛋知道你一定知道什么叫做祖先(从根到某个点的路径上的每个点都是这个点的祖先,包括它本身),也一定知道什么叫做最近公共祖先(两个点的最近公共祖先是某个点,这个点同时是两个点的祖先,且离根最远)。
    现在给出这棵树,你需要求出:\sum_{n}^{i=1}\sum_{n}^{j=1}w[i]*w[j]*w[LCA(i,j)]
其中LCA(i,j)表示点i与点j的最近公共祖先。
由于答案可能很大,你只需要输出它对1,000,000,007取模的结果。

 

输入格式

    第一行为两个整数n w[1]。
    第二行到第n行,第i行有两个整数p[i],w[i]。

 

输出格式

    输出只有一行,为一个整数,表示所求答案对1,000,000,007取模的结果。

样例输入

    2 2

    1 1

样例输出

    17

数据范围与约定

    对于30%的数据,n≤100,w[i]≤10。
    对于60%的数据,n≤1,000,w[i]≤1,000。
    对于100%的数据,1≤n≤100,000,0≤w[i]≤1,000,000,000,1<p[i]<i。

样例解释

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