比赛 “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;
}