比赛 2024暑假C班集训B 评测结果 AAAAAAEEEE
题目名称 Asm.Def的基本算法 最终得分 60
用户昵称 彭欣越 运行时间 1.161 s
代码语言 C++ 内存使用 5.00 MiB
提交时间 2024-07-11 10:23:48
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int mod=1000000007;
long long w[100010],mk[1010][1010],res;
int n,f[100010],flag[100010];
int LCA (int x,int y) {
    int cnt;
    for (int i=x;i;i=f[i]) flag[i]=1;
    for (int i=y;i;i=f[i]) {
        if (flag[i]) {
            cnt=i;
            break;
        }
    }
    for (int i=x;i;i=f[i]) flag[i]=0;
    return cnt;
}
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++) {
        cin >> f[i] >> w[i];
    }
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=n;j++) {
            if (mk[j][i]) {
                res+=mk[j][i];
                res%=mod;
                continue;
            }
            mk[i][j]=w[i]*w[j]*w[LCA(i,j)];
            mk[i][j]%=mod;
            res+=mk[i][j];
            res%=mod;
        }
    }
    cout << res <<endl;
    return 0;
}