记录编号	561086	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011] 聪聪可可	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.028 s
提交时间	2021-06-15 23:31:40	内存使用	3.03 MiB

#include <cstdio>

const int N = 1e5 + 10;
int n, dp[N][3], head[N], nxt[N], w[N], len[N];

void add(int x, int y, int l)
{
	static int cnt = 0;
	w[++cnt] = y;
	len[cnt] = l;
	nxt[cnt] = head[x];
	head[x] = cnt;
}

int ans;

void solve(int x, int fa)
{
	dp[x][0] = 1;
	for (int i = head[x]; i; i = nxt[i])
	if (w[i] != fa){
		int y = w[i], dis = len[i];
		solve(y, x);
		for (int i = 0; i < 3; ++i) ans += dp[x][i] * (dp[y][(6 - dis - i) % 3]);
		for (int i = 0; i < 3; ++i) dp[x][(i + dis) % 3] += dp[y][i];
	}
}

int gcd(int x, int y)
{
	return y ? gcd(y, x % y) : x;
}

int main()
{
	freopen("cckk.in", "r", stdin);
	freopen("cckk.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i < n; ++i)
	{
		int x, y, l;
		scanf("%d%d%d", &x, &y, &l);
		l %= 3;
		add(x, y, l);
		add(y, x, l);
	}
	solve(1, 0);
	ans = ans * 2 + n;
	int total = n * n, d = gcd(ans, total);
	printf("%d/%d\n", ans / d, total / d);
	return 0;
}