BZOJ 2152 聰聰可可：樹上點分治統計權值和為 3 的倍數點對

題目大意

給定一棵 n 個節點的樹，邊權為 0/1/2。求節點對 (u,v) 數量，使得路徑上邊權和模 3 為 0。答案需化為最簡分數 p/q。

核心算法：點分治

點分治是處理樹上路徑問題的利器，核心步驟：

1. 找重心：遞歸計算子樹大小，找到移除後最大子樹最小的節點。
2. 統計過重心的路徑：從重心 DFS 記錄每個節點到重心的距離模 3 值 dep[u] % 3，計數 cnt[0..2]。
3. 組合計算：路徑和模 3 為 0 的組合數 = C(cnt[0],2) + cnt[1]*cnt[2]（含重心自身）。
4. 減去子樹內部：遞歸進入各子樹，同理統計並減去完全在子樹內的路徑（避免重複計數）。
5. 遞歸分治：對每個子樹重複上述過程。

關鍵公式

設 ha[0], ha[1], ha[2] 為當前統計的三類節點數，有效點對數：

ha[0]*ha[0] + ha[1]*ha[2]*2

（有序對，含 (u,u)；最終答案分子為無序對數，分母為 n*n。）

完整代碼（C++）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 20010, INF = 0x3f3f3f3f;
struct Edge { int v, w, nxt; } e[MAXN<<1];
int h[MAXN], ec, n, ans, minSize, root;
int sz[MAXN], dep[MAXN], ha[3], vis[MAXN];

void add(int u, int v, int w) {
    e[ec] = {v, w, h[u]}; h[u] = ec++;
}
void init() {
    memset(h, -1, sizeof h); ec = ans = 0;
    memset(vis, 0, sizeof vis);
}
void getRoot(int u, int fa, int tot) {
    sz[u] = 1; int mx = 0;
    for (int i = h[u]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        if (v == fa || vis[v]) continue;
        getRoot(v, u, tot);
        sz[u] += sz[v];
        mx = max(mx, sz[v]);
    }
    mx = max(mx, tot - sz[u]);
    if (mx < minSize) minSize = mx, root = u;
}
void getDep(int u, int fa) {
    ha[dep[u]%3]++; sz[u] = 1;
    for (int i = h[u]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        if (v == fa || vis[v]) continue;
        dep[v] = dep[u] + e[i].w;
        getDep(v, u);
        sz[u] += sz[v];
    }
}
int calc(int u, int initDep) {
    dep[u] = initDep; ha[0]=ha[1]=ha[2]=0;
    getDep(u, -1);
    return ha[0]*ha[0] + ha[1]*ha[2]*2;
}
void solve(int u) {
    vis[u] = 1;
    ans += calc(u, 0);
    for (int i = h[u]; ~i; i = e[i].nxt) {
        int v = e[i].v;
        if (vis[v]) continue;
        ans -= calc(v, e[i].w);          // 減去子樹內部
        minSize = INF;
        getRoot(v, -1, sz[v]);
        solve(root);
    }
}
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
int main() {
    while (scanf("%d", &n) != EOF) {
        init();
        for (int i = 1, u, v, w; i < n; ++i) {
            scanf("%d%d%d", &u, &v, &w);
            add(u, v, w%3); add(v, u, w%3);
        }
        minSize = INF; getRoot(1, -1, n);
        solve(root);
        int g = gcd(ans, n*n);
        printf("%d/%d\n", ans/g, n*n/g);
    }
    return 0;
}

複雜度分析

• 時間：O(n log n)，每層分治處理所有節點共 O(n)，深度 O(log n)。
• 空間：O(n)。

易錯點提醒

1. 邊權模 3 後再存，避免大數溢出。
2. calc 返回有序對數，最終分子需除 2？本題定義為有序對（含 (u,u)），分母 n*n，直接約分即可。
3. 遞歸深度可能達 n，建議增大棧或改寫非遞歸。