【题面】
不虚就是要AK(czyak.c/.cpp/.pas)
2s 128M
czy很火。因为又有人说他虚了。为了证明他不虚，他决定要在这次比赛AK。
现在他正在和别人玩一个游戏：在一棵树上随机取两个点，如果这两个点的距离是4的倍数，那么算czy赢，否则对方赢。现在czy想知道他能获胜的概率。
以即约分数形式输出这个概率（即“a/b”的形式，其中a和b必须互质。如果概率为1，输出“1/1”）。
本题多组数据。对于每组数据：第一行一个数n，表示树上的节点个数 接下来n-1条边a,b,c描述a到b有一条长度为c的路径 当n=0时表示读入结束
数据组数不超过10
输入数据
5
1 2 1
1 3 2
1 4 1
2 5 3
0
输出数据
7/25
数据范围
| 数据点 | n的规模 | 数据组数 | 随机生成数据 |
| 1 | 200 | 1 | 是 |
| 2 | 200 | 1 | 是 |
| 3 | 200 | <=3 | 是 |
| 4 | 2000 | <=3 | 是 |
| 5 | 2000 | <=3 | 是 |
| 6 | 2000 | <=5 | 是 |
| 7 | 20000 | <=5 | 否 |
| 8 | 20000 | <=5 | 否 |
| 9 | 20000 | <=10 | 否 |
| 10 | 20000 | <=10 | 否 |
【思路】
考虑过树根的情况。
设sum[i]表示前S-1棵子树中dis%4=i的点数，tmp代表当前S子树。
一遍dfs求出dis后累计答案即可。
需要注意的是点对算两次而且路长0算作4的倍数。
【代码】
#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; const int N = +; struct Edge {
int v,w;
Edge(int v=,int w=) :v(v),w(w){}
};
vector<Edge> g[N];
int n,m,k,ans;
int root,size,siz[N],dis[N],f[N],vis[N]; int gcd(int x,int y) { return y==? x:gcd(y,x%y); } void getroot(int u,int fa) {
siz[u]=; f[u]=;
for(int i=;i<g[u].size();i++) {
int v=g[u][i].v;
if(v!=fa && !vis[v]) {
getroot(v,u);
siz[u]+=siz[v];
if(siz[v]>f[u]) f[u]=siz[v];
}
}
f[u]=max(f[u],size-siz[u]);
if(f[u]<f[root]) root=u;
}
int tmp[],sum[];
void dfs(int u,int fa) {
tmp[dis[u]]++;
for(int i=;i<g[u].size();i++) {
int v=g[u][i].v;
if(v!=fa && !vis[v]) {
dis[v]=(dis[u]+g[u][i].w)%;
dfs(v,u);
}
}
}
void solve(int u) {
memset(sum,,sizeof(sum));
vis[u]=; sum[]=;
for(int i=;i<g[u].size();i++) {
int v=g[u][i].v;
if(!vis[v]) {
dis[v]=g[u][i].w%;
dfs(v,u);
for(int j=;j<;j++)
ans+=tmp[j]*sum[(-j)%];
for(int j=;j<;j++)
sum[j]+=tmp[j],tmp[j]=;
}
}
for(int i=;i<g[u].size();i++) {
int v=g[u][i].v;
if(!vis[v]) {
size=siz[v]; root=;
getroot(v,-); solve(root);
}
}
}
void read(int& x) {
char c=getchar(); int f=; x=;
while(!isdigit(c)){if(c=='-') c=-; c=getchar();}
while(isdigit(c)) x=x*+c-'',c=getchar();
x*=f;
}
int main() {
//freopen("in.in","r",stdin);
//freopen("out.out","w",stdout);
while(read(n),n!=) {
ans=;
FOR(i,,n) g[i].clear();
memset(vis,,sizeof(vis));
int u,v,w;
FOR(i,,n-) {
read(u),read(v),read(w);
g[u].push_back(Edge(v,w));
g[v].push_back(Edge(u,w));
}
root=; f[]=1e9; size=n;
getroot(,-) , solve(root);
int b=n*n; ans=ans*+n;
int gc=gcd(ans,b);
printf("%d/%d\n",ans/gc,b/gc);
}
return ;
}