题目链接

Solution [国家集训队]聪聪可可

题目大意：给定一棵带权的树，在树上随机选两个点，问两点间路径长能被\(3\)整除的概率

点分治

---

分析：要算概率的话我们可以求出有多少条路径长能被\(3\)整除，然后一共有\(n^2\)条路径除\(gcd\)约分即可

关于分子，我们要统计树上所有路径，因此我们考虑点分治，两点交换顺序不好考虑我们钦定一个点在前，最后把分子乘上\(2\)加上\(n\)即可（因为两点相同交换后仍然算一种方案）

关于点分治，我们按子树统计，对于每条路径我们看一下之前有多少条路径和它加起来长度可以被\(3\)整除即可

#include <cstdio>
#include <cctype>
#include <vector>
using namespace std;
const int maxn = 2e4 + 100;
inline int read(){
    int x = 0;char c = getchar();
    while(!isdigit(c))c = getchar();
    while(isdigit(c))x = x * 10 + c - '0',c = getchar();
    return x;
}
inline int gcd(int a,int b){return !b ? a : gcd(b,a % b);}
struct Edge{int to,dist;};
vector<Edge> G[maxn];
vector<int> rem;
inline void addedge(int from,int to,int dist){G[from].push_back(Edge{to,dist});}
int maxsiz[maxn],siz[maxn],vis[maxn],dis[maxn],judge[3],tmp[3],n,rt,sum,ans1,ans2;
inline void getroot(int u,int faz = -1){
    siz[u] = 1;maxsiz[u] = 0;
    for(auto e : G[u]){
        int v = e.to;
        if(vis[v] || v == faz)continue;
        getroot(v,u);
        siz[u] += siz[v];
        maxsiz[u] = max(maxsiz[u],siz[v]);
    }
    maxsiz[u] = max(maxsiz[u],sum - siz[u]);
    if(maxsiz[u] < maxsiz[rt])rt = u;
}
inline void getdis(int u,int faz = -1){
    rem.push_back(dis[u]);
    for(auto e : G[u]){
        int v = e.to;
        if(vis[v] || v == faz)continue;
        dis[v] = (dis[u] + e.dist) % 3;
        getdis(v,u);
    }
}
inline void calc(int u){
    for(auto e : G[u]){
        int v = e.to;
        if(vis[v])continue;
        dis[v] = e.dist % 3;
        rem.clear();
        getdis(v,u);
        for(auto x : rem)
            ans1 += judge[(3 - x) % 3];
        for(auto x : rem)
            judge[x]++;
    }
    judge[0] = judge[1] = judge[2] = 0;
}
inline void solve(int u){
    vis[u] = judge[0] = 1;calc(u);
    for(auto e : G[u]){
        int v = e.to;
        if(vis[v])continue;
        sum = siz[v];maxsiz[rt = 0] = 0x7fffffff;
        getroot(v),getroot(rt),solve(rt);
    }
}
int main(){
    n = read();
    for(int u,v,w,i = 1;i < n;i++)
        u = read(),v = read(),w = read(),addedge(u,v,w),addedge(v,u,w);
    sum = n,maxsiz[rt = 0] = 0x7fffffff;
    getroot(1),solve(rt);
    ans1 = ans1 * 2 + n;
    ans2 = n * n;
    int g = gcd(ans1,ans2);
    printf("%d/%d\n",ans1 / g,ans2 / g);
    return 0;
}