[洛谷P2634][国家集训队]聪聪可可

题目大意：给你一棵树，随机选两个点，求它们之间路径长度是$3$的倍数的概率

题解：点分治，求出当前状态的重心，然后求出经过重心的答案，接着分治每棵子树。注意考虑重复计算的情况

卡点：无

C++ Code：

#include <cstdio>

#include <algorithm>

#define maxn 20010

const int inf = 0x3f3f3f3f;

inline int min(int a, int b) {return a < b ? a : b;}

inline int max(int a, int b) {return a > b ? a : b;}

int head[maxn], cnt;

struct Edge {

	int to, nxt, w;

} e[maxn << 1];

inline void add(int a, int b, int c) {

	e[++cnt] = (Edge) {b, head[a], c}; head[a] = cnt;

	e[++cnt] = (Edge) {a, head[b], c}; head[b] = cnt;

}

int n, ans;

bool vis[maxn];

namespace Center_of_Gravity {

	#define n nodenum

	int root, MIN, n;

	int sz[maxn];

	void __getroot(int u, int fa) {

		sz[u] = 1;

		int MAX = 0;

		for (int i = head[u]; i; i = e[i].nxt) {

			int v = e[i].to;

			if (v != fa && !vis[v]) {

				__getroot(v, u);

				sz[u] += sz[v];

				MAX = max(sz[v], MAX);

			}

		}

		MAX = max(n - sz[u], MAX);

		if (MAX < MIN) MIN = MAX, root = u;

	}

	int getroot(int rt, int nodenum) {

		Center_of_Gravity::n = nodenum;

		MIN = inf;

		__getroot(rt, 0);

		return root;

	}

	#undef n

}

using Center_of_Gravity::getroot;

int V[3];

void getlist(int u, int fa, int val) {

	V[val]++;

	for (int i = head[u]; i; i = e[i].nxt) {

		int v = e[i].to;

		if (v != fa && !vis[v]) getlist(v, u, (val + e[i].w) % 3);

	}

}

int calc(int u, int val = 0) {

	V[0] = V[1] = V[2] = 0;

	getlist(u, 0, val);

	return (V[1] * V[2] << 1) + V[0] * V[0];

}

void dfs(int u) {

	ans += calc(u);

	vis[u] = true;

	for (int i = head[u]; i; i = e[i].nxt) {

		int v = e[i].to;

		if (!vis[v]) {

			ans -= calc(v, e[i].w);

			dfs(getroot(v, Center_of_Gravity::sz[v]));

		}

	}

}

int main() {

	scanf("%d", &n);

	for (int i = 1, a, b, c; i < n; i++) {

		scanf("%d%d%d", &a, &b, &c);

		add(a, b, c % 3);

	}

	dfs(getroot(1, n));

	int tmp = std::__gcd(ans, n * n);

	printf("%d/%d\n", ans / tmp, n * n / tmp);

	return 0;

}