相关链接
题目传送门:http://codeforces.com/contest/802/problem/L
官方题解:http://dj3500.webfactional.com/helvetic-coding-contest-2017-editorial.pdf
解题报告
这题告诉我们,这类题可以高斯消元做
裸做是$O(n^3)$的,非常不科学
这题我们发掘性质,如果从叶子开始一层一层往上消,高斯消元那一块可以做到$O(n)$
然后再算上逆元的话,总的时间复杂度:$O(n \log n)$
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 100009; const int M = 200009; const int MOD = 1000000007; int n, head[N], nxt[M], to[M], cost[M]; int a[N], b[N], fa[N], d[N]; inline int read() { char c=getchar(); int f=1,ret=0; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret * f; } inline void AddEdge(int u, int v, int c) { static int E = 1; d[u]++; d[v]++; cost[E + 1] = cost[E + 2] = c; to[++E] = v; nxt[E] = head[u]; head[u] = E; to[++E] = u; nxt[E] = head[v]; head[v] = E; } inline int REV(int x) { int ret = 1, t = MOD - 2; for (; t; x = (LL)x * x % MOD, t >>= 1) { if (t & 1) { ret = (LL)ret * x % MOD; } } return ret; } void solve(int w, int f) { if (d[w] > 1) { a[w] = -1; for (int i = head[w]; i; i = nxt[i]) { b[w] = (b[w] + (LL)cost[i] * REV(d[w])) % MOD; if (to[i] != f) { solve(to[i], w); } } if (w != f) { b[f] = (b[f] - (LL)b[w] * REV((LL)a[w] * d[f] % MOD)) % MOD; a[f] = (a[f] - REV((LL)d[w] * d[f] % MOD) * (LL)REV(a[w])) % MOD; } } } int main() { #ifdef DBG freopen("11input.in", "r", stdin); #endif n = read(); for (int i = 1; i < n; ++i) { int u = read(), v = read(); AddEdge(u + 1, v + 1, read()); } solve(1, 1); int ans = (LL)b[1] * REV(MOD - a[1]) % MOD; ans = (ans + MOD) % MOD; cout<<ans<<endl; return 0; }