记录编号	590812	评测结果	AAAAAAAAAA
题目名称	[SYOI 2015] Asm.Def的基本算法	最终得分	100
用户昵称	彭欣越	是否通过	通过
代码语言	C++	运行时间	0.205 s
提交时间	2024-07-11 18:53:24	内存使用	4.45 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=500010,mod=1000000007;
typedef long long ll;
ll tot,f[N],head[N],sum[N],w[N],ans,n;
struct edge{
    ll x,y,nxt;
}a[N]; 
void add(int x,int y){
    a[++tot].x=x;
    a[tot].y=y;
    a[tot].nxt=head[x];
    head[x]=tot;
}
void dfs (int x) {
    sum[x]=w[x];
    for (int i=head[x];i;i=a[i].nxt){
        if (f[a[i].y]==0){
            f[a[i].y]=x;
            dfs(a[i].y);
            ans=(ans%mod+sum[x]%mod*sum[a[i].y]%mod*w[x]%mod)%mod;
            sum[x]=(sum[x]%mod+sum[a[i].y])%mod;
        }
    }
}
 
int main(){
    freopen("asm_algo.in","r",stdin);
    freopen("asm_algo.out","w",stdout);
    scanf("%lld%lld",&n,&w[1]);     
    for (int i=2;i<=n;i++){
        int a;
        cin >> a >> w[i];
        add(a,i);
    }
    dfs(1);
    ans=(ans%mod*2)%mod;
    for (int i=1;i<=n;i++) ans=(ans%mod+w[i]%mod*w[i]%mod*w[i]%mod)%mod;
    printf("%lld",ans);
    return 0;
}