题意：给出一棵树，求树上任意两个节点的距离为3的倍数在所有距离里占的比例。
思路：点分治求距离为3的倍数的点对有多少。
#include<bits/stdc++.h> #define ll long long using namespace std; const int N = 4e4 + 10; int n, h[N], cnt, sz[N], rt, vis[N], mx, sn; int dep[N], d[4], ans; struct node { int v, w, nt; } no[N]; void add(int u, int v, int w) { no[cnt] = node{v, w, h[u]}; h[u] = cnt++; } void getroot(int u, int fa) { sz[u] = 1; int ma = 0; for(int i = h[u]; ~i; i = no[i].nt) { int v = no[i].v; if(!vis[v] && v != fa) { getroot(v, u); sz[u] += sz[v]; ma = max(ma, sz[v]); } } ma = max(ma, sn - sz[u]); if(mx > ma) mx = ma, rt = u; } void getdep(int u, int fa) { d[dep[u] % 3]++; for(int i = h[u]; ~i; i = no[i].nt) { int v = no[i].v; if(!vis[v] && v != fa) dep[v] = (dep[u] + no[i].w) % 3, getdep(v, u); } } int calc(int u, int v) { memset(d, 0, sizeof d); dep[u] = v % 3; getdep(u, 0); return d[1] * d[2] * 2 + d[0] * d[0]; } void dfs(int u) { vis[u] = 1, ans += calc(u, 0); for(int i = h[u]; ~i; i = no[i].nt) { int v = no[i].v; if(!vis[v]){ ans -= calc(v, no[i].w), sn = sz[v], rt = 0, mx = 1e9, getroot(v, 0), dfs(rt); } } } int main() { memset(h, -1, sizeof h); scanf("%d", &n); for(int u, v, w, i = 1; i < n; i++) { scanf("%d%d%d", &u, &v, &w); add(u, v, w), add(v, u, w); } sn = n, mx = 1e9, getroot(1, 0), dfs(rt); int r = __gcd(ans, n * n); cout << ans / r << "/" << n * n / r << endl; return 0; }
