比赛 “Asm.Def战记之太平洋”杯 评测结果 AAAAAAAAAA
题目名称 Asm.Def的基本算法 最终得分 100
用户昵称 debug 运行时间 0.219 s
代码语言 C++ 内存使用 8.34 MiB
提交时间 2015-11-02 11:57:37
显示代码纯文本
#include<cstdio>
using namespace std;
long long n;
long long v[111111]={};
long long gen[111111]={};
long long shuliang[111111]={};
long long weizhi[111111]={};
long long weizhi2[111111]={};
long long q[111111]={};
long long rudu[111111]={};
long long zishuquanzhi[111111]={};
long long tou,wei;
long long sum=0;
long long ans=0;
int linkk[111111]={};
struct ff
{
	int x,y;
}bian[111111]={};
int top=0;
int main()
{
	freopen("asm_algo.in","r",stdin);
	freopen("asm_algo.out","w",stdout);
	scanf("%d%d",&n,&v[1]);
	for(int i=2;i<=n;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		v[i]=b;
		shuliang[a]++;
		bian[++top].x=a,bian[top].y=i;
		gen[i]=a;
	}
	for(int i=2;i<=n+1;i++)
		weizhi[i]=weizhi2[i]=weizhi[i-1]+shuliang[i-1];
	for(int i=1;i<=top;i++)
		linkk[weizhi2[bian[i].x]]=bian[i].y,weizhi2[bian[i].x]++;
	tou=0,wei=-1;
	for(int i=1;i<=n;i++)
		if(shuliang[i]==0)
			q[++wei]=i;
	for(int i=1;i<=n;i++)
		zishuquanzhi[i]=v[i];
	for(int i=1;i<=n;i++)
		rudu[i]=shuliang[i];
	rudu[1]++;
	while(tou<=wei)
	{
		int te=q[tou];
		rudu[gen[te]]--;
		zishuquanzhi[gen[te]]=(zishuquanzhi[gen[te]]+zishuquanzhi[te])%1000000007;
		if(rudu[gen[te]]==0)
			q[++wei]=gen[te];
		tou++;
	}
	tou=0,wei=-1;
	q[++wei]=1;
	for(int i=1;i<=n;i++)
		ans=(ans+v[i]*v[i]%1000000007*v[i])%1000000007;//自己和自己之间
	while(tou<=wei)//子树和子树
	{
		int te=q[tou];
		for(int i=weizhi[te];i<weizhi[te+1];i++)
			if(shuliang[linkk[i]]>0)
				q[++wei]=linkk[i];
		long long tm=0;
		for(int i=weizhi[te];i<weizhi[te+1];i++)
			tm=tm+zishuquanzhi[linkk[i]];
		long long tm2=0;
		for(int i=weizhi[te];i<weizhi[te+1];i++)
			tm2=(tm2+(tm-zishuquanzhi[linkk[i]])%1000000007*zishuquanzhi[linkk[i]])%1000000007;
		tm2=tm2*v[te]%1000000007;
		ans=(ans+tm2)%1000000007;
		tou++;
	}
	//自己和子树
	tou=0,wei=-1;
	q[++wei]=1;
	while(tou<=wei)
	{
		int te=q[tou];
		for(int i=weizhi[te];i<weizhi[te+1];i++)
			q[++wei]=linkk[i];
		long long tm=0;
		for(int i=weizhi[te];i<weizhi[te+1];i++)
			tm=tm+zishuquanzhi[linkk[i]];
		tm=tm%1000000007;
		ans=(ans+v[te]*v[te]*2%1000000007*tm)%1000000007;
		tou++;
	}
	printf("%d\n",ans);
	return 0;
}