记录编号	202921	评测结果	AAAAAAAAAA
题目名称	[SYOI 2015] Asm.Def的基本算法	最终得分	100
用户昵称	devil	是否通过	通过
代码语言	C++	运行时间	0.524 s
提交时间	2015-11-02 12:32:57	内存使用	2.99 MiB

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <ctime>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef unsigned int uint;
const int inf=1061109567;
const int maxn=100010;
const int maxm=100010;
const int mod=1000000007;
const double pi=3.14;

vector<int> G[maxn];
ll sum[maxn];
ll w[maxn],ans=0;

ll mul(ll a,ll b)
{
    ll c=0;
    while(b)
    {
        if(b&1) c=(c+a)%mod;
        b>>=1;a=(a+a)%mod;
    }
    return c%mod;
}

void build_tree(int u)
{
    int len=G[u].size();
    ll tmp1=0,tmp2=0,tmp=0;
    for(int i=0;i<len;i++)
    {
        int v=G[u][i];
        build_tree(v);
        sum[u]+=sum[v];sum[u]%=mod;
        tmp1+=sum[v];tmp+=sum[v];
        tmp2+=(sum[v]*sum[v])%mod;
        tmp1%=mod;tmp2%=mod;tmp%=mod;
    }
    tmp=(tmp*tmp-tmp2)%mod;tmp*=w[u];
    tmp1*=(w[u]*w[u])%mod;tmp1*=2;
    tmp%=mod;tmp1%=mod;ans+=tmp;ans+=tmp1;
    sum[u]+=w[u];ans%=mod;sum[u]%=mod;
}

int main()
{
    freopen("asm_algo.in","r",stdin);
    freopen("asm_algo.out","w",stdout);
    //clock_t st=clock();
    int n,p;scanf("%d%lld",&n,&w[1]);
    ans+=mul(mul(w[1],w[1]),w[1]);ans%=mod;
    for(int i=2;i<=n;i++)
    {
        scanf("%d%lld",&p,&w[i]);
        G[p].push_back(i);
        ans+=mul(mul(w[i],w[i]),w[i]);ans%=mod;
    }
    build_tree(1);
    printf("%lld\n",ans%mod);
    //clock_t ed=clock();
    //printf("\nTime used : %.5lf Ms\n",double(ed-st)/CLOCKS_PER_SEC);
    return 0;
}