比赛 |
2024暑假C班集训B |
评测结果 |
TTTTTTTTTT |
题目名称 |
Asm.Def的基本算法 |
最终得分 |
0 |
用户昵称 |
dream |
运行时间 |
19.979 s |
代码语言 |
C++ |
内存使用 |
3.09 MiB |
提交时间 |
2024-07-11 10:48:53 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int N=10005,mod=1e9+7;
int w[N];
int n;
int fa[N];
int mk[N];
int cnt;
int jyh[N][N];
int read(){
char c;
int f=1,sum=0;
c=getchar();
while(c<'0'||c>'9'){
if(c=='-'){
f=-1;
}
c=getchar();
}
while(c>='0'&&c<='9'){
sum=sum*10+c-'0';
c=getchar();
}
return sum*f;
}
void add(int x,int y){
fa[x]=y;
}
int lca(int x,int y){
int flag=0;
if(x<y){
swap(x,y);
flag=1;
}
for(int i=1;i<=n;i++){
mk[i]=0;
}
for(int i=x;i!=1;i=fa[i]){
// cout<<fa[i]<<" ";
mk[i]=1;
}
for(int i=y;i;i=fa[i]){
if(mk[i]){
if(!flag){
jyh[x][y]=i;
}
if(flag){
jyh[y][x]=i;
}cout<<"";
return i;
}
}
}
int main(){
freopen("asm_algo.in","r",stdin);
freopen("asm_algo.out","w",stdout);
n=read();
w[1]=read();
fa[1]=0;
for(int i=2;i<=n;i++){
int p;
p=read();
w[i]=read();
add(i,p);
}
int res=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int lcaa;
if(!jyh[i][j]){
lcaa=lca(i,j);
}
else{
lcaa=jyh[i][j];
}
int ans=1;
ans*=w[i];
ans%=mod;
ans*=w[j];
ans%=mod;
ans*=w[lcaa];
ans%=mod;
res+=ans;
res%=mod;
}
}
cout<<res;
return 0;
}