朴素的O(n2logn)显然会爆，我们需要优化。
这种有公式的题目，我们可以从公式入手，化简公式，简化运算。
其中最常见的就是提取公因式。
这个公式有三个因子，显然lca对于我们来说方便处理些。
我们假设一个点i为某两点的lca，考察它对答案的贡献。
第一种情况就是两点分别在i的不同子树内，设以该点为根的子树的总权值和为sum[i]，则对答案的贡献为$\sum _{i'}sum\left( i'\right) \left( sum\left( i\right) -sum\left( i'\right) \right)$ (i'为i的儿子)
第二种情况就是有个点在lca上，则对答案的贡献为$V\left( i\right) \ast sum\left( i\right)$（其中算了一次两个点在lca上）
累加起来就可以了。
1 #include <cstdio>神奇的代码
2 #include <cstring>
3 #include <iostream>
4 #define N 1005005
5 #define mo 1000000007
6 using namespace std;
7 int head[N],next[N],to[N],num,size[N],n,m;
8 long long ans,sum[N],va[N];
9 void add(int u,int v){
10 num++;
11 next[num]=head[u];
12 to[num]=v;
13 head[u]=num;
14 }
15 void DFS(int x){
16 size[x]=1;
17 sum[x]=va[x];
18 for (int v,i=head[x];i;i=next[i]){
19 v=to[i];
20 DFS(v);
21 size[x]+=size[v];
22 sum[x]=(sum[v]+sum[x])%mo;
23 }
24 }
25 void QAQ(int x){
26 if (size[x]==1) {ans=(va[x]*va[x]%mo*va[x]%mo+ans)%mo; return;}
27 for (int v,i=head[x];i;i=next[i]){
28 v=to[i];
29 QAQ(v);
30 ans=((sum[v])*(sum[x]-sum[v])%mo*va[x]%mo+ans)%mo;
31 }
32 ans=((sum[x]*va[x])%mo*(va[x])%mo+ans)%mo;
33 }
34 int main(){
35 num=0;
36 scanf("%d%lld",&n,&va[1]);
37 for (int u,i=2;i<=n;++i){
38 scanf("%d%lld",&u,&va[i]);
39 add(u,i);
40 }
41 ans=0;
42 DFS(1);
43 QAQ(1);
44 printf("%lld\n",ans%mo);
45 return 0;
46 }