描述 Description
聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）…… 遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画 n 个 “点”，并用 n-1 条“边” 把这 n 个 “点” 恰好连通（其实这就是一棵树）。并且每条 “边” 上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是 3 的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。
输入格式 InputFormat
输入的第 1 行包含 1 个正整数 n。后面 n-1 行，每行 3 个整数 x、y、w，表示 x 号点和 y 号点之间有一条边，上面的数是 w。
输出格式 OutputFormat
以即约分数形式输出这个概率（即 “a/b” 的形式，其中 a 和 b 必须互质。如果概率为 1，输出“1/1”）。
样例输入 SampleInput
5
1 2 1
1 3 2
1 4 1
2 5 3
样例输出 SampleOutput
13/25
点分治，只需要统计边权除以三余数为 0,1,2 的情况即可。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int inf = 0x7fffffff / 27.11;
const int maxn = 10005;
const int maxm = maxn * 2;
int i, j, t, n, m, l, r, k, z, y, x;
struct edge
{
int to, vl, nx;
} e[maxm];
int head[maxn], dis[maxn], a[maxn], son[maxn];;
bool vis[maxn];
int cnt, num, ans, len, siz, c;
void dfs(int u, int fa)
{
int i, t, v;
son[u] = 1;
for (t = 0, i = head[u]; i; i = e[i].nx)
{
v = e[i].to;
if (!vis[v] && v != fa)
{
dfs(v, u);
son[u] += son[v];
t = max(t, son[v]);
}
}
t = max(t, m - son[u]);
if (t < siz) c = u, siz = t;
}
int getcenter(int s)
{
c = 0; siz = inf;
dfs(s, -1);
return c;
}
inline void ins(int u, int v, int w)
{
e[++cnt] = (edge)
{
v, w, head[u]
}; head[u] = cnt;
e[++cnt] = (edge)
{
u, w, head[v]
}; head[v] = cnt;
}
void getarray(int u, int fa)
{
int i, v, w;
a[++len] = dis[u];
for (i = head[u]; i; i = e[i].nx)
{
v = e[i].to; w = e[i].vl;
if (!vis[v] && v != fa) dis[v] = dis[u] + w, getarray(v, u);
}
}
int calc(int u, int now)
{
int ans = 0;
dis[u] = now; len = 0;
getarray(u, -1);
sort(a + 1, a + len + 1);
l = 1; r = len;
while (l < r)
{
if (a[r] + a[l] <= k) ans += (r - l), l++;
else r--;
}
return ans;
}
void solve(int s)
{
int i, v, w;
ans += calc(s, 0);
vis[s] = true;
for (i = head[s]; i; i = e[i].nx)
{
v = e[i].to; w = e[i].vl;
if (!vis[v])
{
ans -= calc(v, w);
m = son[v];
r = getcenter(v);
solve(r);
}
}
}
int main()
{
while (scanf("%d%d", &n, &k) != EOF)
{
cnt = 0;
if (n == 0 && k == 0) break;
memset(head, 0, sizeof(head));
memset(vis, 0, sizeof(vis));
for (i = 1; i < n; i++) scanf("%d%d%d", &x, &y, &z), ins(x, y, z);
ans = 0;
m = n;
r = getcenter(1);
solve(r);
printf("%d\n", ans);
}
return 0;
}