比赛 “Asm.Def战记之太平洋”杯 评测结果 MMMMMMMMMM
题目名称 Asm.Def的基本算法 最终得分 0
用户昵称 WINAPI 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2015-11-02 11:28:21
显示代码纯文本
#include<stdio.h>
#include<cstring>
struct aa
{
	int num;
	int d[1000];
}tree[100001];
int a[100001][1001];
int d[400001][65];
int p[100001];
int num1[100001];
int pos[100001];
int f[100001];
int w[100001];
int t=-1;
int t1=0;
int n;
long long ans=0;
int max(int x,int y)
{
	if(x>y) return x;
	else return y; 
}
int min(int x,int y)
{
	if(x>y) return y;
	else return x;
}
int built_tree(int x)
{
	int j=0;
 	for(int i=1;i<=a[x][0];i++)
 	 if(!p[a[x][i]])
	 {
	 	p[a[x][i]]=1;
	 	j++;
	 	tree[x].d[j]=a[x][i];
	 	built_tree(a[x][i]);
	 }
	 tree[x].d[0]=j;
	return 0; 
}
int dfs1(int x)
{
	t++;
	t1++;
	tree[x].num=t1;
	num1[t1]=x; 
	f[t]=t1;
	for(int i=1;i<=tree[x].d[0];i++)
	 if(tree[x].d[i]!=0)
	  {
	  	dfs1(tree[x].d[i]);
	 	t++;
	 	f[t]=tree[x].num;
	  }
	return 0;  
}
int build(int j)
{
	p[j]=1; 
	built_tree(j);
	dfs1(j);
	return 0;
}
int built()
{
	for(int i=0;i<t;i++)
	 d[i][0]=f[i];
	for(int j=1;(1<<j)<=t;j++)
	 for(int i=0;i+(1<<j)-1<t;i++)
	  d[i][j]=min(d[i][j-1],d[i+(1<<(j-1))][j-1]);
	return 0;   
}
int query(int l,int r)
{
	int k=0;
	while(1<<(k+1)<=r-l+1) k++;
	return min(d[l][k],d[r-(1<<k)+1][k]);
}
int m,x,y,z;
int main()
{
	freopen("asm_algo.in","r",stdin);
	freopen("asm_algo.out","w",stdout);
	scanf("%d",&n);
	scanf("%d",&w[1]);
	for(int i=2;i<=n;i++)
	{
		scanf("%d%d",&x,&w[i]);
		a[i][0]++; 
		a[x][0]++;
		a[x][a[x][0]]=i;
		a[i][a[i][0]]=x;
	}
//	for(int i=1;i<=n;i++)
//		printf("%d ",w[i]);
	build(1);//建树
	t++;
	built();
	memset(p,0,sizeof(p));
	for(int i=0;i<t;i++)
	 if(!p[f[i]])
	 {
	 	pos[f[i]]=i;
	 	p[f[i]]=1;
	 }
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
	 {
	 	int z=query(min(pos[tree[i].num],pos[tree[j].num]),max(pos[tree[j].num],pos[tree[i].num]));
//	 	ans=ans+(w[z]*w[i]*w[j]);
		ans+=(((long long)w[z]%1000000007)*((long long)w[i]%1000000007)*((long long)w[j]%1000000007))%1000000007;
	 }
	 	printf("%lld",ans);
}