比赛 “Asm.Def战记之太平洋”杯 评测结果 AAAAAAAAAA
题目名称 Asm.Def的基本算法 最终得分 100
用户昵称 Satoshi 运行时间 0.310 s
代码语言 C++ 内存使用 3.46 MiB
提交时间 2015-11-02 09:57:00
显示代码纯文本
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define N 100010
using namespace std;
typedef long long ll;
ifstream in("asm_algo.in");
ofstream out("asm_algo.out");
int n;
ll w[N]={0};//权值
vector<int> G[N];
bool l[N]={0};
int cnt[N]={0};
ll mod=1000000007,ans=0;
ll f[N]={0};//权值和
void DFS(int u)
{
	int i,v;
	l[u]=1;
	f[u]=w[u];
	for(i=0;i<G[u].size();i++)
	{
		v=G[u][i];
		if(!l[v])
		{
			cnt[u]++;
			DFS(v);
			f[u]+=f[v];
			f[u]%=mod;
		}
	}
}
void BFS(int u)
{
	int i,v;
	ll temp=0,solo=0,ok,poi=0,boi=0;
	l[u]=1;
	for(i=0;i<G[u].size();i++)
	{
		v=G[u][i];
		if(!l[v])
		{
			BFS(v);
			temp+=f[v];
			poi+=(f[v]*f[v])%mod;
			solo+=f[v];
			solo%=mod;temp%=mod;poi%=mod;
		}
	}
	if(!cnt[u])return ;
	boi=(temp*temp-poi)%mod;//上
	boi*=w[u];
	solo*=(w[u]*w[u])%mod;
	solo*=2;
	boi%=mod;solo%=mod;
	ans+=boi;
	ans+=solo;
	ans%=mod;
}
void read()
{
	int i,u,v;
	in>>n>>w[1];
	for(i=2;i<=n;i++)
	{
		in>>u>>w[i];
		G[i].push_back(u);
		G[u].push_back(i);
	}
}
void work()
{
	int i;
	ll temp=0,solo=0;
	DFS(1);
	for(i=1;i<=n;i++)l[i]=0;
	BFS(1);
	for(i=1;i<=n;i++)
	{
		temp=w[i];
		temp*=w[i];temp%=mod;
		temp*=w[i];temp%=mod;
		solo+=temp;
		solo%=mod;
	}
	ans+=solo;
	ans%=mod;
	out<<ans<<endl;
}
int main()
{
	read();
	work();
	return 0;
}