比赛 |
“Asm.Def战记之太平洋”杯 |
评测结果 |
AAAAAATTTT |
题目名称 |
Asm.Def的基本算法 |
最终得分 |
60 |
用户昵称 |
Apocana-Wisbtsml |
运行时间 |
4.227 s |
代码语言 |
C++ |
内存使用 |
1.38 MiB |
提交时间 |
2018-11-07 16:53:54 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<vector>
#define ll long long
#define rint register int
using namespace std;
const int maxn = 100001;
const int mod = 1e9 + 7;
inline int read() {
int x = 0, f = 1; char ch = getchar();
for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;
for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ 48);
return x * f;
}
struct node {
int next, to;
}edge[maxn << 1];
int n, m, num = 0, w[maxn], h[maxn] = {0}, fa[maxn];
ll sum[maxn], ans = 0, shu = 0;
inline void add(rint a, rint b) {
edge[++num].next = h[a];
edge[num].to = b;
h[a] = num;
}
void dfs(rint u) {
sum[u] = w[u];
for(rint i = h[u]; i; i = edge[i].next) {
int v = edge[i].to;
if(fa[u] != v) {
fa[v] = u;
dfs(v);
ans = (ans + sum[u] * sum[v] % mod * 1ll * w[u] % mod) % mod;
sum[u] = (sum[u] + sum[v]) % mod;
}
}
}
inline int _main() {
freopen("asm_algo.in", "r", stdin); freopen("asm_algo.out", "w", stdout);
n = read(); w[1] = read(); shu = 1ll * w[1] * w[1] % mod * w[1] % mod; fa[1] = 0;
for(rint i = 2, p; i <= n; ++i) {
p = read(); w[i] = read();
add(i, p); add(p, i);
shu = (shu + 1ll * w[i] * w[i] % mod * w[i] % mod) % mod;
}
dfs(1);
ans = ans * 2 % mod;
ans = (ans + shu) % mod;
printf("%lld", ans);
return 0;
}
int jiasu = _main();
int main(){;}