比赛 2024暑假C班集训B 评测结果 AAAAAAATTT
题目名称 Asm.Def的基本算法 最终得分 70
用户昵称 LikableP 运行时间 7.022 s
代码语言 C++ 内存使用 3.85 MiB
提交时间 2024-07-11 09:59:06
显示代码纯文本
#include <iostream>
#include <fstream>
using namespace std;

const int MAXN = 1e5 + 10;
const int MAXM = 1e5 + 10;
const int MOD = 1e9 + 7;

int head[MAXN], edgeNum;
struct EDGE{int from, to, next, w;}edge[MAXM];
int father[MAXN], depth[MAXN];

void AddEdge(int from, int to){
	edgeNum++;
	edge[edgeNum].to = to;
	edge[edgeNum].next = head[from];
	head[from] = edgeNum;
}

void dfs(int x, int father){
	::father[x] = father;
	depth[x] = depth[father] + 1;
	for(int i = head[x]; i; i = edge[i].next){
		if(edge[i].to != father){
			dfs(edge[i].to, x);
		}
	}
}

int getLCA(int x, int y){
	while(x != y){
		if(depth[x] >= depth[y]){
			x = father[x];
		}else{
			y = father[y];
		}
	}
	return x;
}

int n;
long long ans;
long long w[MAXN];

int main(){
	freopen("asm_algo.in", "r", stdin);
	freopen("asm_algo.out", "w", stdout);
	cin >> n >> w[1];
	for(int i = 2; i <= n; i++){
		int p, w;
		cin >> p >> w;
		AddEdge(p, i);
		::w[i] = w % MOD;
	}
	
	dfs(1, 1);
	
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			long long s1 = w[i] * w[j] % MOD;
			long long s2 = s1 * w[getLCA(i, j)] % MOD;
			ans += s2;
			ans %= MOD;
		}
	}
	
	cout << ans;
	return 0;
}