比赛 |
“Asm.Def战记之太平洋”杯 |
评测结果 |
AAAAWWWWWW |
题目名称 |
Asm.Def的基本算法 |
最终得分 |
40 |
用户昵称 |
devil |
运行时间 |
0.201 s |
代码语言 |
C++ |
内存使用 |
2.99 MiB |
提交时间 |
2015-11-02 10:13:38 |
显示代码纯文本
#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;
void build_tree(int u)
{
int len=G[u].size();
ll tmp1=0,tmp2=0;
for(int i=0;i<len;i++)
{
int v=G[u][i];
build_tree(v);
sum[u]+=sum[v];
tmp1+=sum[v];
tmp2+=(sum[v]*sum[v])%mod;
tmp1%=mod;tmp2%=mod;
}
sum[u]+=w[u];
ans+=(((((w[u]*w[u])%mod)*tmp1)%mod)*2)%mod;
ans%=mod;tmp1=(tmp1*tmp1)%mod;
ans+=w[u]*(tmp1-tmp2);ans%=mod;
}
int main()
{
freopen("asm_algo.in","r",stdin);
freopen("asm_algo.out","w",stdout);
//clock_t st=clock();
int n,p;scanf("%d%d",&n,&w[1]);
ans+=(((w[1]*w[1])%mod)*w[1])%mod;ans%=mod;
for(int i=2;i<=n;i++)
{
scanf("%d%d",&p,&w[i]);
G[p].push_back(i);
ans+=(((w[i]*w[i])%mod)*w[i])%mod;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;
}