比赛 “Asm.Def战记之太平洋”杯 评测结果 AAAAAAWWWW
题目名称 Asm.Def的基本算法 最终得分 60
用户昵称 Regnig Etalsnart 运行时间 0.099 s
代码语言 C++ 内存使用 4.23 MiB
提交时间 2018-11-07 14:07:46
显示代码纯文本
#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<cmath>
#define MOD 1000000007
using namespace std;
int n,fa[1001][20],w[1001],LCA[1001][1001];
int maxdep,dep[1001],vis[1001],ans=0;
vector<int>G[1001];
void swap(int &x,int &y){x^=y;y^=x;x^=y;}
void dfs(int now)
{
	vis[now]=1;
	for(int i=0;i<G[now].size();i++)
	{
		int to=G[now][i];
		if(!vis[to])
		{
			dep[to]=dep[now]+1;
			dfs(to);
		}
	}
	return;
}
void getfa()
{
	for(int j=1;j<=maxdep;j++)for(int i=1;i<=n;i++)
		fa[i][j]=fa[fa[i][j-1]][j-1];
	return;
}
int work(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	int deep=dep[x]-dep[y];
	for(int j=maxdep;j>=0;j--)
		if(deep&(1<<j))x=fa[x][j];
	if(x==y)return x;
	for(int j=maxdep;j>=0;j--)
	{
		if(fa[x][j]!=fa[y][j])
		{
			x=fa[x][j];
			y=fa[y][j];
		}
	}
	return fa[x][0];
}
int main()
{
	freopen("asm_algo.in","r",stdin);
	freopen("asm_algo.out","w",stdout);
	memset(vis,0,sizeof(vis));
	scanf("%d%d",&n,&w[1]);
	fa[1][0]=0;
	for(int i=2;i<=n;i++)
	{
		scanf("%d%d",&fa[i][0],&w[i]);
		G[i].push_back(fa[i][0]);
		G[fa[i][0]].push_back(i);
	}
	maxdep=log(n)/log(2)+1;
	dep[1]=0;
	dfs(1);
	getfa();
	for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)
	{
		int lca=work(i,j);
		LCA[i][j]=lca;
		LCA[j][i]=lca;
	}
	for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
	{
		int res=(((w[i]*w[j])%MOD)*w[LCA[i][j]])%MOD;
		ans=(ans+res)%MOD;
	}
	printf("%d\n",ans);
	return 0;
}