洛谷P2634 [国家集训队] 聪聪可可题解

题意：

聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。

他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画 $n$ 个“点”，并用 $n-1$ 条“边”把这 $n$ 个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随机选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是 $3$ 的倍数，则判聪聪赢，否则可可赢。

聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

输入格式：

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

输出格式：

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

数据范围：

对于 $100\%$ 的数据，$n\leq 2 \times 10^4$。

本题从各方面来说还是比较简单的，就是点分治板子而已。

我们可需要统计所有满足条件的情况，然后除以 $n^2$ 就是答案概率了（记得约分）

统计的方式类似于 P4178 Tree （也是点分治板子），需要去掉不合法的路径。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(4e4 + 15))

int n, m, rt, rt_fa, res, sum, pos = 1;
int head[N], sz[N], mx[N], q[N], dis[N], ans[3]; char vis[N];
int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
struct Edge { int u, v, w, next; } e[N * 2];
void addEdge(int u, int v, int w) {
    e[++pos] = {u, v, w, head[u]}; head[u] = pos;  
}
void getroot(int u, int fa)
{
    mx[u] = 0; sz[u] = 1;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v; if(v == fa || vis[v]) continue;
        getroot(v, u); sz[u] += sz[v]; up(mx[u], sz[v]);
    }
    up(mx[u], sum - sz[u]); if(mx[u] < mx[rt]) { rt = u, rt_fa = fa; }
}
void getdis(int u, int fa)
{
    ++ans[dis[u]];
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v; if(v == fa || vis[v]) continue;
        dis[v] = (dis[u] + e[i].w) % 3; getdis(v, u);
    }
}
int calc(int u, int w)
{
    memset(ans, 0, sizeof(ans));
    dis[u] = w; getdis(u, 0);
    return ans[2] * ans[1] * 2 + ans[0] * ans[0];
}
void solve(int u)
{
    vis[u] = true; res += calc(u, 0);
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v; if(vis[v]) continue;
        res -= calc(v, e[i].w % 3);
        sum = v == rt_fa ? n - sz[u] : sz[v];
        mx[rt = rt_fa = 0] = n; getroot(v, u); solve(rt);
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; 
    for(int i = 1, u, v, w; i < n; i++)
    {
        cin >> u >> v >> w;
        addEdge(u, v, w); addEdge(v, u, w);
    }
    mx[rt = rt_fa = 0] = sum = n;
    getroot(1, 0); solve(rt);
    int g = gcd(res, n * n);
    cout << res / g << '/' << n * n / g << '\n';
    return 0;
}