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