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