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
",ans1 / g,ans2 / g);
return 0;
}