比赛 “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(){;}