P2634-[国家集训队]聪聪可可
题目:
题目描述:
聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。
他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画 $n$ 个“点”，并用 $n-1$ 条“边”把这 $n$ 个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是 $3$ 的倍数，则判聪聪赢，否则可可赢。
聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。
输入格式:
输入的第 $1$ 行包含 $1$ 个正整数 $n$。后面 $n-1$ 行，每行 $3$ 个整数 $x, y, w$，表示 $x$ 号点和 $y$ 号点之间有一条边，上面的数是 $w$。
输出格式:
以即约分数形式输出这个概率（即 a/b 的形式，其中 $a$ 和 $b$ 必须互质。如果概率为 $1$，输出 1/1 ）。
样例:
样例输入1:
1
2
3
4
5
| 5
1 2 1
1 3 2
1 4 1
2 5 3
|
样例输出1:
思路:
实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include "ybwhead/ios.h"
long long ans, full;
int n;
const int maxn = 1e5 + 10;
struct edge
{
int v, w, nxt;
} e[maxn << 1];
int tot, head[maxn];
void __ADD(int u, int v, int w)
{
e[++tot].v = v;
e[tot].w = w;
e[tot].nxt = head[u];
head[u] = tot;
}
void add(int u, int v, int w)
{
__ADD(u, v, w);
__ADD(v, u, w);
}
int mod(int x)
{
return (x % 3 + 3) % 3;
}
long long f[maxn][3];
void dfs(int u, int fa)
{
// cout << u << endl;
f[u][0] = 1;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v, w = e[i].w;
if (v == fa)
continue;
dfs(v, u);
for (int i = 0; i < 3; i++)
ans += f[v][i] * f[u][mod(-i - w)];
for (int i = 0; i < 3; i++)
f[u][mod(i + w)] += f[v][i];
}
}
long long gcd(long long a, long long b)
{
if (!b)
return a;
return gcd(b, a % b);
}
int main()
{
yin >> n;
for (int i = 1; i < n; i++)
{
int a, b, c;
yin >> a >> b >> c;
add(a, b, c);
}
dfs(1, 0);
ans <<= 1;
ans += n;
full = n * n;
long long gc = gcd(full, ans);
full /= gc;
ans /= gc;
yout << ans << "/" << full << endl;
return 0;
}
|