比赛 |
“Asm.Def战记之太平洋”杯 |
评测结果 |
|
题目名称 |
Asm.Def的基本算法 |
最终得分 |
0 |
用户昵称 |
CloudTower |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2018-11-07 19:44:47 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<vector>
#define ll long long
using namespace std;
const int mod=1e9+7;
struct edge{
ll nxt,to;
}e[100010];
ll head[100010],cnt,dp[100010],ans,fa[100010],w[100010],n;
void add(ll x,ll y)
{
e[++cnt].to=y;
e[cnt].nxt=head[x];
head[x]=cnt;
}
ll sum[100010];
void dfs(ll x)
{
sum[x]+=w[x];
for(ll i=head[x];i;i=e[i].nxt)
{
ll v=e[i].to;
if(v==fa[x])continue;
dfs(v);
sum[x]=(sum[x]+sum[v])%mod;
}
}
void calc(ll x)
{
dp[x]=0;
int tmp=w[x];
for(ll i=head[x];i;i=e[i].nxt)
{
ll v=e[i].to;
if(v==fa[x])continue;
dp[x]=(dp[x]+sum[v]%mod*w[x]%mod*tmp%mod*2%mod)%mod;
tmp=(tmp+sum[v])%mod;
}
dp[x]=(dp[x]%mod+w[x]%mod*w[x]%mod*w[x]%mod)%mod;
}
int main()
{
freopen("asm_algo.in","r",stdin);
freopen("asm_algo.out","w",stdout);
cin>>n>>w[1];
for(ll i=2;i<=n;i++)
{
cin>>fa[i]>>w[i];
add(fa[i],i);
}
dfs(1);
for(ll i=1;i<=n;i++)
{
calc(i);ans=(ans+dp[i])%mod;
}
cout<<ans;
return 0;
}