记录编号	393341	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011] 聪聪可可	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.076 s
提交时间	2017-04-10 18:50:25	内存使用	1.25 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
#include <deque>
#include <cctype>
using namespace std;
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char readc(){
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?0:*fs++;
  }
  template<typename T>
  inline void splay(T &r){
    char c; bool s = false;
    while((c = readc())){
      if(c >= '0' && c <= '9'){
        r = c^0x30; break;
      }else if(c == '-')s = true;
    }while(isdigit(c = readc()))
      r = r*10+(c^0x30);
    if(s)r = -r;
  }
}using IO::splay;
const int MAXN = 2e4+10;
int n, div_size;
int root;
int size[MAXN], wei[MAXN];
bool vis[MAXN];
int cnt[3];
struct edge{
  int to, val, next;
}es[MAXN*2]; int head[MAXN], _etot;
void addedge(int u, int v, int c){
  es[++_etot] = (edge){v, c, head[u]}; head[u] = _etot;
  es[++_etot] = (edge){u, c, head[v]}; head[v] = _etot;
}
void get_root(int u, int f){
  size[u] = 1;
  int son = 0;
  for(int i = head[u]; i; i = es[i].next){
    int to = es[i].to; if(to == f || vis[to])continue;
    get_root(to, u);
    size[u] += size[to];
    if(size[son] < size[to])son = to;
  }
  wei[u] = max(size[son], div_size-size[son]);
  if(!root || wei[root] > wei[u])root = u;
}
void dfs(int u, int f, int d){
  cnt[d]++;
  for(int i = head[u]; i; i = es[i].next){
    int to = es[i].to; if(to == f || vis[to])continue;
    dfs(to, u, (d+es[i].val)%3);
  }
}
int calc(int u, int d = 0){
  cnt[0] = cnt[1] = cnt[2] = 0;
  dfs(u, 0, d);
  return cnt[0]*cnt[0]+cnt[1]*cnt[2]*2;
}
int all = 0;
void div_solve(int u){
  div_size = size[u];
  vis[u] = true;
  int ans = calc(u);
  for(int i = head[u]; i; i = es[i].next){
    int to = es[i].to; if(vis[to])continue;
    ans -= calc(to, es[i].val);
    
    root = 0;
    div_size = size[to];
    get_root(to, u);
    div_solve(root);
  }
  all += ans;
}
int gcd(int x, int y){
  return y?gcd(y, x%y):x;
}
void solve(){
  root = 0;
  div_size = n;
  get_root(1, 0);
  div_solve(root);
  int S = n*n; int d = gcd(all, S);
  printf("%d/%d\n", all/d, S/d);
}
int main(){
  //freopen("test_data.txt", "r", stdin);
  freopen("cckk.in", "r", stdin);
  freopen("cckk.out", "w", stdout);
  splay(n);
  for(int i = 1; i < n; i++){
    int x, y, w; splay(x); splay(y); splay(w);
    addedge(x, y, w%3);
  }
  solve();
  return 0;
}