bzoj2152 聪聪可可

Description

聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画 \(n\) 个“点”，并用 \(n-1\) 条“边”把这 \(n\) 个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是 \(3\) 的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

Input

输入的第 \(1\) 行包含 \(1\) 个正整数 \(n(n\leq 20000)\) 。后面 \(n-1\) 行，每行 \(3\) 个整数 \(x,y,w\)，表示 \(x\) 号点和 \(y\) 号点之间有一条边，上面的数是 \(w\) 。

Output

以即约分数形式输出这个概率（即“ \(a/b\) ”的形式，其中 \(a\) 和 \(b\) 必须互质。如果概率为 \(1\) ，输出“ \(1/1\) ”）。

Sample Input

5
1 2 1
1 3 2
1 4 1
2 5 3

Sample Output

13/25

Solution

点分治。记录一个大小为 \(3\) 的数组，分别统计 \(\mod 3\) 为 \(0,1,2\) 的路径条数即可。

#include<bits/stdc++.h>
using namespace std;

#define N 40005
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define drp(i, a, b) for (int i = a; i >= b; i--)
#define fech(i, x) for (int i = 0; i < x.size(); i++)

inline int read() {
    int x = 0, flag = 1; char ch = getchar(); while (!isdigit(ch)) { if (!(ch ^ '-')) flag = -1; ch = getchar(); }
    while (isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); return x * flag;
}

inline void write(int x) {
    if (!x) { putchar('0'); return; } if (x < 0) putchar('-'), x = -x;
    char buf[20] = ""; int top = 0; while (x) buf[++top] = x % 10 + '0', x /= 10; while (top) putchar(buf[top--]);
}

int n;
struct edgeType { int u, v, w; }eg[N]; int tot;
#define getEg edgeType e = eg[g[u][i]]
vector<int> g[N];
bool vis[N];
int Size[N], mx[N], sum, root;
int t[3], d[N];
int ans;

int TG(int a, int b) { return b ? TG(b, a % b) : a; }

void getRoot(int u, int fa) {
    Size[u] = 1; mx[u] = 0;
    fech(i, g[u]) {
        getEg; if (!(e.v ^ fa) || vis[e.v]) continue;
        getRoot(e.v, u); Size[u] += Size[e.v], mx[u] = max(mx[u], Size[e.v]);
    }
    mx[u] = max(mx[u], sum - Size[u]);
    if (mx[u] < mx[root]) root = u;
}

void calcDis(int u, int fa) {
    t[d[u]]++;
    fech(i, g[u]) {
        getEg; if (!(e.v ^ fa) || vis[e.v]) continue;
        d[e.v] = (d[u] + e.w) % 3; calcDis(e.v, u);
    }
}

int calc(int u, int w) { d[u] = w; t[0] = t[1] = t[2] = 0; calcDis(u, 0); return t[1] * t[2] * 2 + t[0] * t[0]; }
void work(int u) {
    ans += calc(u, 0); vis[u] = 1;
    fech(i, g[u]) {
        getEg; if (vis[e.v]) continue;
        //要去重
        ans -= calc(e.v, e.w); root = 0; sum = Size[e.v]; getRoot(e.v, 0); work(root);
    }
}

int main() {
    n = read(); rep(i, 2, n) {
        int u = read(), v = read(), w = read() % 3;
        eg[++tot] = edgeType{ u, v, w }, g[u].push_back(tot);
        eg[++tot] = edgeType{ v, u, w }, g[v].push_back(tot);
    }
    mx[0] = sum = n; getRoot(1, 0); work(root);
    int t = TG(ans, n * n); printf("%d/%d", ans / t, n * n / t);
    return 0;
}