比赛 2024暑假C班集训B 评测结果 AAAAAAEEEE
题目名称 Asm.Def的基本算法 最终得分 60
用户昵称 123 运行时间 0.993 s
代码语言 C++ 内存使用 4.32 MiB
提交时间 2024-07-11 10:43:39
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int N=100010,Mod=1e9+7,M=1010;
int flag[N],n,w[N],p[N],dp[M][M];
long long ret=0;
int LCA(int a,int b) 
{
    for (int i=a;i;i=p[i])
    {
        flag[i]=1;
    }
    int cnt=0;
    for (int i=b;i;i=p[i])
    {
        if (flag[i])
        {
            cnt=i;
            break;
        }
    }
    for (int i=a;i;i=p[i])
    {
        flag[i]=0;
    }
    return cnt;
}
int main() {
    freopen("asm_algo.in","r",stdin);
    freopen("asm_algo.out","w",stdout);
    scanf("%d%d",&n,&w[1]);
    for (int i=2;i<=n;i++)
    {
        scanf("%d%d",&p[i],&w[i]);
    }
    for (int i=1;i<=n;i++)
    {
        for (int j=1;j<=n;j++)
        {
            if (dp[j][i])
            {
                ret+=dp[j][i];
                ret%=Mod;
                continue;
            }
            dp[i][j]=w[i]*w[j]*w[LCA(i,j)];
            dp[i][j]%=Mod;
            ret+=dp[i][j];
            ret%=Mod;
        }
    }
    cout<<ret;
}