比赛 2024暑假C班集训B 评测结果 AAAAAAAAAA
题目名称 Asm.Def的基本算法 最终得分 100
用户昵称 liuyiche 运行时间 0.208 s
代码语言 C++ 内存使用 7.70 MiB
提交时间 2024-07-11 09:25:54
显示代码纯文本
#include <bits/stdc++.h>
            
using namespace std;

typedef long long ll;

int n;
int mod = 1000000007;
ll anss = 0;
struct node
{
    vector<int> nxt;
    ll w;
    ll cnt;
    ll ans;    
};
vector<node> v(100005);

inline ll dfs(int step)
{
    for(int i = 0; i < v[step].nxt.size(); ++i)
    {
        v[step].cnt += dfs(v[step].nxt[i]);
        v[step].cnt %= mod;
    }
    v[step].cnt += v[step].w;
    v[step].cnt %= mod;
    return v[step].cnt;
}

inline void dfs2(int step)
{
    v[step].ans = 0;
    ll tmp = v[step].cnt;
    tmp -= v[step].w;
    for(int i = 0; i < v[step].nxt.size(); ++i)
    {
        v[step].ans += (((v[step].w*v[step].w)%mod)*v[v[step].nxt[i]].cnt)%mod;
        v[step].ans %= mod;
    }
    for(int i = 0; i < v[step].nxt.size(); ++i)
    {
        ll a = v[v[step].nxt[i]].cnt;
        tmp -= a;
        v[step].ans += (((a*v[step].w)%mod)*tmp)%mod;
        v[step].ans %= mod;
    }
    for(int i = 0; i < v[step].nxt.size(); ++i)
        dfs2(v[step].nxt[i]);
}
    
int main()
{
    freopen("asm_algo.in", "r", stdin);
    freopen("asm_algo.out", "w", stdout);
        
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
            
    cin >> n >> v[1].w;
    for(int i = 1; i <= n; ++i)
        v[i].cnt = 0;
    for(int i = 2; i <= n; ++i)
    {
        int p;
        ll w;
        cin >> p >> w;
        v[p].nxt.push_back(i);
        v[i].w = w;
    }
    
    dfs(1);
    dfs2(1);
    
    for(int i = 1; i <= n; ++i)
    {
        anss += v[i].ans;
        anss %= mod;
    }
    anss *= 2;
    anss %= mod;
    for(int i = 1; i <= n; ++i)
    {
        anss += (((v[i].w*v[i].w)%mod)*v[i].w)%mod;
        anss %= mod;
    }
    
    cout << anss;
    
   	return 0;
}