比赛 2024暑假C班集训B 评测结果 AAAAAAAAAA
题目名称 Asm.Def的基本算法 最终得分 100
用户昵称 ┭┮﹏┭┮ 运行时间 0.100 s
代码语言 C++ 内存使用 4.10 MiB
提交时间 2024-07-11 08:38:21
显示代码纯文本
#include <bits/stdc++.h> 
using namespace std;
#define ll long long
const int N = 1e5+10;
const ll mod = 1e9+7;

ll read(){
    ll x = 0,f = 1;char c = getchar();
    for(;c < '0' || c > '9';c = getchar())if(c == '-')f = -1;
    for(;c >= '0' && c <= '9';c = getchar())x = (x<<1) + (x<<3) + c-'0';
    return x * f;
}

int n;
ll f[N],v[N],sum[N],ans;
struct made{
    int ver,nx;
}e[N<<1];
int hd[N],tot;
void link(int x,int y){e[++tot] = {y,hd[x]},hd[x] = tot;}

void dfs(int x){
    ll tmp = 0;
    sum[x] = v[x];
    for(int i = hd[x];i;i = e[i].nx){
        int y = e[i].ver;
        dfs(y);
        (sum[x] += sum[y]) %= mod;
        (f[x] += tmp * sum[y] % mod) %= mod;
        (tmp += sum[y]) %= mod;
    }
    (f[x] += tmp * v[x] % mod) %= mod;
}

int main(){
    freopen("asm_algo.in","r",stdin);
    freopen("asm_algo.out","w",stdout);
    n = read(),v[1] = read();
    for(int i = 2;i <= n;i++){
        int y = read();v[i] = read();
        link(y,i);
    }
    dfs(1);
    for(int i = 1;i <= n;i++)ans = (ans + 2ll * v[i] % mod * f[i] % mod + v[i] * v[i] % mod * v[i] % mod) % mod;
    printf("%lld\n",ans);
    
    
    return 0;
    
}