题解 P2634 【[国家集训队]聪聪可可】（待填坑）
pantw
2018-01-22 00:05:21
emmm先丢着吧，之后有时间了再来写题解。
写法其实是跟别的题解学的辣qaq
```cpp
// luogu-judger-enable-o2
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 20010
#define maxm 40010
#define INF 0x3F3F3F3F
#define Lovelive long long
using namespace std;
inline int r() {
char c = getchar();
int x = 0;
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') x = 10 * x + c - '0', c = getchar();
return x;
}
inline int max(int a, int b) {
return a > b ? a : b;
}
Lovelive gcd(Lovelive a, Lovelive b) {
return b ? gcd(b, a % b) : a;
}
int n, k;
int head[maxn], nxt[maxm], to[maxm], weight[maxm], ec;
Lovelive cnt[10];
int siz[maxn], dis[maxn], sum, root, rtson;
bool vis[maxn];
Lovelive ans;
void add(int u, int v, int w) {
nxt[++ec] = head[u];
head[u] = ec;
weight[ec] = w;
to[ec] = v;
}
void getroot(int x, int fa) {
int son = 0; siz[x] = 1;
for(int e = head[x]; e; e = nxt[e]) if(to[e] != fa && !vis[to[e]]) getroot(to[e], x), siz[x] += siz[to[e]], son = max(son, siz[to[e]]);
if((son = max(son, sum - siz[x])) < rtson) root = x, rtson = son;
}
void dfs(int x, int fa) {
cnt[dis[x]]++;
for(int e = head[x]; e; e = nxt[e]) if(to[e] != fa && !vis[to[e]]) dis[to[e]] = (dis[x] + weight[e]) % 3, dfs(to[e], x);
}
Lovelive query(int x, int d) {
cnt[0] = cnt[1] = cnt[2] = 0;
dis[x] = d % 3;
dfs(x, 0);
Lovelive ret = cnt[0] * cnt[0] + cnt[1] * cnt[2] * 2;
return ret;
}
void solve(int x) {
ans += query(x, 0);
vis[x] = true;
for(int e = head[x]; e; e = nxt[e]) {
if(vis[to[e]]) continue;
ans -= query(to[e], weight[e]);
sum = siz[to[e]];
rtson = INF;
getroot(to[e], 0);
solve(root);
}
}
int main() {
n = r();
ans = ec = 0;
for(int i = 1; i < n; i++) {
int u, v, w;
u = r(), v = r(), w = r();
add(u, v, w);
add(v, u, w);
}
rtson = INF;
sum = n;
getroot(1, 0);
solve(root);
Lovelive g = gcd(ans, (Lovelive)n * n);
printf("%lld/%lld\n", ans / g, (Lovelive) n * n / g);
return 0;
}
```