聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是3的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

输入的第1行包含1个正整数n。后面n-1行，每行3个整数x、y、w，表示x号点和y号点之间有一条边，上面的数是w。

以即约分数形式输出这个概率（即“a/b”的形式，其中a和b必须互质。如果概率为1，输出“1/1”）。

/

#include<stdio.h>

#include<string.h>

#define N 20010

#define dmax(x,y) ((x)>(y)?(x):(y))

inline int Rin(){

  int x=,c=getchar(),f=;

  for(;c<||c>;c=getchar())

    if(!(c^))f=-;

  for(;c>&&c<;c=getchar())

    x=(x<<)+(x<<)+c-;

  return x*f;

}

inline int gcd(int x,int y){

  int k;

  while(y){

    k=x%y;

    x=y;

    y=k;

  }

  return x;

}

bool vis[N];

int n,fst[N],ecnt,ans,root,sum,d[N],ind[],f[N],size[N];

struct edge{

  int v,w,nxt;

}e[N<<];

inline void link(int x,int y,int w){

  e[++ecnt].v=y;

  e[ecnt].w=w;

  e[ecnt].nxt=fst[x];

  fst[x]=ecnt;

}

void getroot(int x,int fa){

  f[x]=;

  size[x]=;

  for(int j=fst[x];j;j=e[j].nxt)

    if(e[j].v^fa&&!vis[e[j].v])

      getroot(e[j].v,x),

      size[x]+=size[e[j].v],

      f[x]=dmax(f[x],size[e[j].v]);

  f[x]=dmax(f[x],sum-size[x]);

  if(f[x]<=f[root])root=x;

}

void getdeep(int x,int fa){

  ind[d[x]]++;

  for(int j=fst[x];j;j=e[j].nxt)

    if(e[j].v^fa&&!vis[e[j].v])

      d[e[j].v]=(d[x]+e[j].w)%,

      getdeep(e[j].v,x);

}

int calc(int x,int w){

  ind[]=ind[]=ind[]=,d[x]=w,getdeep(x,);

  return ind[]*ind[]*+ind[]*ind[];

}

void solve(int x){

  ans+=calc(x,),vis[x]=;

  for(int j=fst[x];j;j=e[j].nxt)

    if(!vis[e[j].v])

      ans-=calc(e[j].v,e[j].w),

      sum=size[e[j].v],root=,

      getroot(e[j].v,),

      solve(root);

}

int main(){

  n=Rin();

  for(int i=;i<n;i++){

    int x=Rin(),y=Rin(),w=Rin()%;

    link(x,y,w),link(y,x,w);

  }

  sum=f[]=n,

  getroot(,),

  solve(root);

  int t=gcd(ans,n*n);

  printf("%d/%d\n",ans/t,n*n/t);

  return ;

}