记录编号	521551	评测结果	AAAAAAAAAA
题目名称	[SYOI 2015] Asm.Def的基本算法	最终得分	100
用户昵称	RainyC	是否通过	通过
代码语言	C++	运行时间	0.087 s
提交时间	2018-11-07 14:41:47	内存使用	3.75 MiB

#include<iostream>
#include<cstdio>
using namespace std;

struct E{
    int to;
    E* nxt;
    E(int to,E* nxt){
        this->to = to;
        this->nxt=nxt;
    }
};

typedef long long int_t;
#define int int_t
#define maxn 100020
#define mod 1000000007

E* head[maxn];
int_t dp[maxn];//以i为lca的答案
int_t sss[maxn];//以i为根的子树权值和
int_t w[maxn];//权值
int fa[maxn];

void addEdge(int a,int b){
    head[a] = new E(b,head[a]);
    head[b] = new E(a,head[b]);
}

void dfs(int rt){
    sss[rt] = w[rt];
    for(E* e= head[rt];e;e=e->nxt){
        int to = e->to;
        if(to==fa[rt])continue;
        fa[to]=rt;
        dfs(to);
        sss[rt]=(sss[rt]+sss[to])%mod;
    }
    
}

void dop(int rt){
    dp[rt]=0;
    int_t temp=w[rt];
    for(E* e= head[rt];e;e=e->nxt){
        int to = e->to;
        if(fa[rt]==to)continue;
        dp[rt] = (dp[rt]+temp*sss[to]*2%mod*w[rt]%mod)%mod;
        temp+=sss[to];temp%=mod;
    }
    dp[rt] = dp[rt]+w[rt]*w[rt]%mod*w[rt]%mod;dp[rt]%=mod;
}

signed main(){ 
    freopen("asm_algo.in","r",stdin);
    #ifndef _debug_   
        freopen("asm_algo.out","w",stdout);
    #endif
    ios::sync_with_stdio(false);
    int n;cin>>n>>w[1];
    w[1]%=mod;
    for(int i=2;i<=n;i++){
        int p;cin>>p>>w[i];
        w[i]%=mod;
        addEdge(p,i);
    }
    dfs(1);
    //cout<<1<<endl;
    int_t ans = 0;
    for(int i=1;i<=n;i++){
        dop(i);
        //cout<<i<<" "<<dp[i]<<endl;
        ans = (ans+dp[i])%mod;
    }
    cout<<ans;
}