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