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