点分治常规题。练习模板
//OJ 2077
//by Cydiater
//2016.9.23
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <queue>
#include <map>
#include <ctime>
#include <cmath>
#include <iomanip>
#include <cstdlib>
using namespace std;
#define ll long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define down(i,j,n) for(int i=j;i>=n;i--)
const int MAXN=1e6+5;
const int oo=0x3f3f3f3f;
inline int read(){
char ch=getchar();int x=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int LINK[MAXN],len=0,sum,max_siz[MAXN],root,siz[MAXN],dis[MAXN],head,tail,q[MAXN],cnt[3],ans=0;
bool vis[MAXN];
struct edge{
int y,next,v;
}e[MAXN<<1];
int N;
namespace solution{
inline void insert(int x,int y,int v){e[++len].next=LINK[x];LINK[x]=len;e[len].y=y;e[len].v=v;}
inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}
void init(){
N=read();
memset(vis,0,sizeof(vis));
up(i,2,N){
int x=read(),y=read(),v=read();
insert(x,y,v);
insert(y,x,v);
}
}
void make_root(int node,int fa){
max_siz[node]=0;siz[node]=1;
for(int i=LINK[node];i;i=e[i].next)if(!vis[e[i].y]&&e[i].y!=fa){
make_root(e[i].y,node);
siz[node]+=siz[e[i].y];
max_siz[node]=max(max_siz[node],siz[e[i].y]);
}
max_siz[node]=max(max_siz[node],sum-max_siz[node]);
if(max_siz[node]<max_siz[root])root=node;
}
void get_deep(int node,int fa){
q[++tail]=dis[node];
for(int i=LINK[node];i;i=e[i].next)if(e[i].y!=fa&&!vis[e[i].y]){
dis[e[i].y]=dis[node]+e[i].v;
get_deep(e[i].y,node);
}
}
int col(int node,int dist){
dis[node]=dist;head=1;tail=0;
get_deep(node,0);
cnt[0]=cnt[1]=cnt[2]=0;
up(i,head,tail)cnt[q[i]%3]++;
return cnt[0]*cnt[0]+2*cnt[1]*cnt[2];
}
void work(int node){
ans+=col(node,0);
vis[node]=1;
for(int i=LINK[node];i;i=e[i].next)if(!vis[e[i].y]){
ans-=col(e[i].y,e[i].v);
root=0;
make_root(e[i].y,node);
work(root);
}
}
void slove(){
sum=N;max_siz[0]=oo;root=0;
make_root(1,0);
work(root);
}
void output(){
int d=gcd(ans,N*N);
printf("%d/%d\n",ans/d,N*N/d);
}
}
int main(){
//freopen("input.in","r",stdin);
using namespace solution;
init();
slove();
output();
return 0;
}