比赛 2024暑假C班集训B 评测结果 AAAAAAAWWW
题目名称 Asm.Def的基本算法 最终得分 70
用户昵称 flyfree 运行时间 0.203 s
代码语言 C++ 内存使用 4.13 MiB
提交时间 2024-07-11 10:28:29
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 400010
#define mod 1000000007
ll n,w[MAXN],ans,idx;
ll hd[MAXN],ed[MAXN],nxt[MAXN];
ll p[MAXN],siz[MAXN];
void build(ll x,ll y){
    nxt[++idx]=hd[x];
    hd[x]=idx;
    ed[idx]=y;
}
void dfs(ll now){
    for(int i=hd[now];i;i=nxt[i]){
        int y=ed[i];
        dfs(y);
        siz[now]=(siz[now]+siz[y])%mod;
    }
    siz[now]=(siz[now]+w[now])%mod;
    ll cnt=0,ansz=0;
    for(int i=hd[now];i;i=nxt[i]){
        int y=ed[i];
        cnt++;
        ansz=(ansz+(siz[y]*(siz[now]-siz[y])*w[now])%mod)%mod;
//ansz=(ansz*siz[y])%mod;
    }
    ansz=(ansz+(w[now]*(siz[now]-w[now])*w[now])%mod)%mod;
    ans=(ans+ansz)%mod;
//    ans=(ans+ansz*w[now])%mod;
    return;
}
int main(){
    freopen("asm_algo.in","r",stdin);
    freopen("asm_algo.out","w",stdout);
    cin>>n>>w[1];
    for(int i=2;i<=n;i++){
        cin>>p[i]>>w[i]; 
//        cin>>w[i]>>p[i];
        build(p[i],i);
    }
    dfs(1);
//    ll ansz=w[now];
    for(int i=1;i<=n;i++){
        ans=(ans+(w[i]*w[i]*w[i])%mod)%mod;
    }
    cout<<ans;
    return 0;
}