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