思路：组成几个联通块，把所有不磨烂的方案算出来就可以了，最后求一个逆元。
/************************************************************************* > Author: wzw-cnyali > Created Time: 2017/3/12 14:09:15 ************************************************************************/ #include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> using namespace std; typedef unsigned long long LL; #define REP(i, a, b) for(register int i = (a), i##_end_ = (b); i <= i##_end_; ++ i) #define DREP(i, a, b) for(register int i = (a), i##_end_ = (b); i >= i##_end_; -- i) #define debug(...) fprintf(stderr, __VA_ARGS__) #define mem(a, b) memset((a), b, sizeof(a)) template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } int read() { int sum = 0, fg = 1; char c = getchar(); while(c < '0' || c > '9') { if (c == '-') fg = -1; c = getchar(); } while(c >= '0' && c <= '9') { sum = sum * 10 + c - '0'; c = getchar(); } return sum * fg; } const int Size = 200010; const int inf = 0x3f3f3f3f; const LL mod = 1e9 + 7; LL C[Size][5]; void get_C(int n) { REP(i, 0, n) { C[i][0] = 1; C[i][i <= 3 ? i : 3] = 1; } REP(i, 1, n) REP(j, 1, i <= 3 ? i : 3) C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod; } int be[Size], to[Size], nxt[Size], w[Size], e; void add(int x, int y, int z) { to[e] = y; nxt[e] = be[x]; be[x] = e; w[e] = z; e++; } int size[Size], id[Size], cnt; bool vis[Size]; void dfs(int x) { vis[x] = 1; for(int i = be[x]; i != -1; i = nxt[i]) { int v = to[i]; if(vis[v]) continue; if(!w[i]) { id[v] = id[x]; ++size[id[v]]; } else { id[v] = ++cnt; ++size[cnt]; } dfs(v); } } LL extend_gcd(LL a, LL b, LL &x, LL &y) { if(!b) { x = 1; y = 0; return a; } LL gcd = extend_gcd(b, a % b, y, x); y -= a / b * x; return gcd; } LL inv(LL p) { LL x, y, gcd = extend_gcd(p, mod, x, y); return gcd == 1 ? ((x + mod) % mod) : -1; } void init(int n) { get_C(n); mem(be, -1); e = 0; } int main() { int n = read(); init(n); REP(i, 1, n - 1) { int x = read(), y = read(), z = read(); add(x, y, z); add(y, x, z); } size[1] = id[1] = cnt = 1; dfs(1); LL sum = C[n][3], ans1 = 0; REP(i, 1, cnt) { if(size[i] == 1) continue; ans1 = ((ans1 + C[size[i]][3]) % mod + (C[size[i]][2] * (n - size[i])) % mod) % mod; } LL ans = ((sum - ans1 + mod) % mod * inv(sum) + mod) % mod; printf("%lld\n", ans); return 0; }
