洛谷【P2634】聪聪可可(点分治)

题解
tmp数组保存当前子树所有节点到重心距离，如果当前距离mod3=0则答案加上1再加上之前子树到重心距离mod3=0的点的个数；如果当前距离mod3=1则答案加上之前子树到重心距离mod3=2的点的个数；如果当前距离mod3=2则答案加上之前子树到重心距离mod3=1的点的个数。最后答案加上n与n^2取个gcd输出概率即可

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e4 + 5;
vector<pair<int, int> >edge[maxn];
int n, m, rt, sum, cnt, ans;
int tmp[maxn], siz[maxn], dis[maxn], maxp[maxn], ***[3];
bool vis[maxn];

inline int read(){
    int s = 0, w = 1; char ch = getchar();
    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

inline void print(int x){
    if(x < 0) x = ~x + 1, putchar('-');
    if(x > 9) print(x / 10);
    putchar(x % 10 + '0');
}

void dfs(int u, int f){///找重心
    siz[u] = 1, maxp[u] = 0;
    for(int i = 0; i < edge[u].size(); i++){
        int v = edge[u][i].first;
        if(v == f || vis[v]) continue;
        dfs(v, u);
        siz[u] += siz[v];
        if(siz[v] > maxp[u]) maxp[u] = siz[v];
    }
    maxp[u] = max(maxp[u], sum - siz[u]);
    if(maxp[u] < maxp[rt]) rt = u;
}

void dfs1(int u, int f){///统计当前子树的所有节点到根节点的距离
    tmp[cnt++] = dis[u];
    for(int i = 0; i < edge[u].size(); i++){
        int v = edge[u][i].first;
        if(v == f || vis[v]) continue;
        dis[v] = dis[u] + edge[u][i].second;
        dfs1(v, u);
    }
}

void solve(int u){///更新答案
    memset(***, 0, sizeof(***));
    for(int i = 0; i < edge[u].size(); i++){
        int v = edge[u][i].first;
        if(vis[v]) continue;
        cnt = 0;
        dis[v] = edge[u][i].second;
        dfs1(v, u);
        for(int j = 0; j < cnt; j++){
            if(tmp[j] % 3 == 0) ans++, ans += ***[0];
            else if(tmp[j] % 3 == 1) ans += ***[2];
            else ans += ***[1];
        }
        for(int j = 0; j < cnt; j++)
            ***[tmp[j] % 3]++;
    }
}

void divide(int u){///点分治
    vis[u] = true;
    solve(u);
    for(int i = 0; i < edge[u].size(); i++){
        int v = edge[u][i].first;
        if(vis[v]) continue;
        maxp[rt = 0] = sum = siz[v];
        dfs(v, 0);
        dfs(rt, 0);
        divide(rt);
    }
}

int main(){
    n = read();
    for(int i = 1; i < n; i++){
        int u = read(), v = read(), w = read();
        edge[u].push_back(make_pair(v, w));
        edge[v].push_back(make_pair(u, w));
    }
    maxp[0] = sum = n;
    dfs(1, 0);
    dfs(rt, 0);
    divide(rt);
    int gcd = __gcd(ans * 2 + n, n * n);
    print((ans * 2 + n) / gcd);
    putchar('/');
    print(n * n / gcd);

    return 0;
}
/*
* ┌───┐   ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐
* │Esc│   │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│  ┌┐    ┌┐    ┌┐
* └───┘   └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘  └┘    └┘    └┘
* ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
* │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
* ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
* │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │   │
* ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
* │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter  │               │ 4 │ 5 │ 6 │   │
* ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤     ┌───┐     ├───┼───┼───┼───┤
* │ Shift  │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│  Shift   │     │ ↑ │     │ 1 │ 2 │ 3 │   │
* ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
* │ Ctrl│ Win│ Alt│         Space         │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │   0   │ . │←─┘│
* └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
*/