「BZOJ-2152」聪聪可可-点分治

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

链接

BZOJ2152

题解

题意：就是给定一棵树，求距离为 $3$ 的倍数的有序点对。
点分治:
对于每个重心统计出每棵子树距离重心长度为 $0,1,2$ 的点的数量，计算出 $ans$ 即可，最后 $ans\times2+1$ 和 $n^2$进行一下约分即可。

代码

#include <bits/stdc++.h>
inline char read() {
    static const int IO_LEN = 1024 * 1024;
    static char buf[IO_LEN], *ioh, *iot;
    if (ioh == iot) {
        iot = (ioh = buf) + fread(buf, 1, IO_LEN, stdin);
        if (ioh == iot) return -1;
    }
    return *ioh++;
}
template<class T>
inline void read(T &x) {
    static char ioc;
    static bool iosig = 0;
    for (iosig = 0, ioc = read(); !isdigit(ioc); ioc = read()) if (ioc == '-') iosig = 1;
    for (x = 0; isdigit(ioc); ioc = read()) x = (x << 1) + (x << 3) + (ioc ^ '0');
    if (iosig) x = -x;
}
const int MAXN = 20000 + 10;
struct Node {
    int v, w;
    Node(int v, int w) : v(v), w(w) {}
};
std::vector<Node> edge[MAXN];
inline void addEdge(int u, int v, int w) {
    edge[u].push_back(Node(v, w));
    edge[v].push_back(Node(u, w));
}
int n, size, son[MAXN], f[MAXN], root, dis[MAXN], ans;
int count[5];
bool vis[MAXN];
inline void getRoot(int u, int father) {
    son[u] = 1, f[u] = 0;
    for (register int i = 0, v; i < edge[u].size(); i++)
        if ((v = edge[u][i].v) != father && !vis[v])
            getRoot(v, u), son[u] += son[v], f[u] = std::max(f[u], son[v]);
    f[u] = std::max(f[u], size - son[u]);
    if (f[u] < f[root]) root = u;
}
inline void getDeep(int u, int father) {
    count[dis[u]]++;
    for (register int i = 0, v; i < edge[u].size(); i++)
        if ((v = edge[u][i].v) != father && !vis[v])
            dis[v] = (dis[u] + edge[u][i].w) % 3, getDeep(v, u);
}
inline int calc(int u, int init) {
    count[0] = count[1] = count[2] = 0, dis[u] = init, getDeep(u, 0);
    return count[1] * count[2] * 2 + count[0] * count[0];
}
inline void work(int u) {
    ans += calc(u, 0), vis[u] = true;
    for (register int i = 0, v; i < edge[u].size(); i++)
        if (!vis[v = edge[u][i].v])
            ans -= calc(v, edge[u][i].w), f[0] = size = son[v], getRoot(v, root = 0), work(root);
}
inline int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }
int main() {
    read(n);
    for (register int i = 1, u, v, w; i < n; i++)
        read(u), read(v), read(w), addEdge(u, v, w % 3);
    f[0] = size = n;
    getRoot(1, 0);
    work(root);
    register int t = gcd(ans, n * n);
    std::cout << ans / t << "/" << n * n / t;
    return 0;
}