[bzoj 2152] 聪聪可可

一棵n个结点的边带权的无根树, 求独立随机选择的两点路径长度恰是3的倍数的概率. (n≤2*10^4) 和CF某题类似, DP求不拐弯的链的数目, 在所有链的lca处统计答案.

const int N = 2e4;
struct Edge {
	int v, w;
};
vector<Edge> adj[N + 1];
int dp[N + 1][3], a;

void dfs(int u, int p)
{
	dp[u][0] = 1;
	Rep (i, 0, adj[u].size()) {
		int v = adj[u][i].v, w = adj[u][i].w;
		if (v == p) continue;
		dfs(v, u);
		Rep (j, 0, 3) a += dp[u][j] * dp[v][(6-j-w)%3];
		Rep (j, 0, 3) dp[u][(j+w)%3] += dp[v][j];
	}
}

int gcd(int a, int b)
{
	return b ? gcd(b, a%b) : a;
}

int main()
{
	int n;
	scanf("%d", &n);
	Rep (i, 0, n-1) {
		int x, y, w;
		scanf("%d%d%d", &x, &y, &w);
		w %= 3;
		adj[x].push_back((Edge){y, w});
		adj[y].push_back((Edge){x, w});
	}
	dfs(1, 0);
	a = a*2 + n;
	int b = n*n, g = gcd(a, b);
	printf("%d/%d\n", a/g, b/g);
	return 0;
}