聰聰和可可是兄弟倆，他們倆經常為了一些瑣事打起來，例如家中只剩下最后一根冰棍而兩人都想吃、兩個人都想玩兒電腦（可是他們家只有一臺電腦）……遇到這種問題，一般情況下石頭剪刀布就好了，可是他們已經玩兒膩了這種低智商的游戲。他們的爸爸快被他們的爭吵煩死了，所以他發明了一個新游戲：由爸爸在紙上畫n個“點”，并用n-1條“邊”把這n個“點”恰好連通（其實這就是一棵樹）。并且每條“邊”上都有一個數。接下來由聰聰和可可分別隨即選一個點（當然他們選點時是看不到這棵樹的），如果兩個點之間所有邊上數的和加起來恰好是3的倍數，則判聰聰贏，否則可可贏。聰聰非常愛思考問題，在每次游戲后都會仔細研究這棵樹，希望知道對于這張圖自己的獲勝概率是多少。現請你幫忙求出這個值以驗證聰聰的答案是否正確。
Input
輸入的第1行包含1個正整數n。后面n-1行，每行3個整數x、y、w，表示x號點和y號點之間有一條邊，上面的數是w。
Output
以即約分數形式輸出這個概率（即“a/b”的形式，其中a和b必須互質。如果概率為1，輸出“1/1”）。
Sample Input
5
1 2 1
1 3 2
1 4 1
2 5 3
Sample Output
13/25
【樣例說明】
13組點對分別是(1,1) (2,2) (2,3) (2,5) (3,2) (3,3) (3,4) (3,5) (4,3) (4,4) (5,2) (5,3) (5,5)。
【數據規模】
對于100%的數據，n<=20000。
要求樹上任意兩點的路徑，我們就可以用點分治做。
如果還不了解什么是點分治可以移步看我之前的一篇博客：POJ 1741tree-點分治入門
和那道題不同的是，這道題需要求路徑為3的倍數的個數。
我們用GetDis函數處理出Dis數組以后，要對Dis數組處理一下，不妨用Cnt數組分別記錄路徑模3余0、1、2的個數。然后總的為3的倍數的路徑就為Cnt[1]*Cnt[2]*2+Cnt[0]*Cnt[0]。為什么是這個樣子呢？
點分治中記錄的路徑包含了從重心到其他所有點的路徑長度，包含到它本身。我們選取的兩個點由樣例看出來是可以重復的。因此我們要考慮選取排列，這樣更方便計數。因為選取的是排列，所以長度為3的倍數的路徑的組成可能有以下幾種：
- 一個長度為余1的和一個長度為余2的，這樣的排列數有
2*Cnt[1]*Cnt[2] - 兩個長度為余0的，這樣的排列數有
Cnt[0]*Cnt[0]（包含到重心本身）
因此總共加起來就是上面的結果。
剩下的就是點分治的基本操作了。
還需要注意開空間，因為保存的是無向邊，所以要開二倍空間。最好一般還是開大一些，也不會吃虧。雖然這道題也沒有爆long long,，但是還是需要注意，可能是因為數據比較弱。如果數據比較強的話是可能溢出的。(有乘法)。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<queue>
#include<set>
#include<map>
#include<cmath>using namespace std;const int MAXN=2e4+5;
typedef long long ll;
struct edge
{int to,len,last;
}Edge[MAXN<<2]; int Last[MAXN],tot;
int n,kk,SonNum[MAXN],MaxNum[MAXN],Vis[MAXN],Dis[MAXN];
int root,rootx,dlen,ss;
ll ans;
ll Cnt[3];int getint()
{int x=0,sign=1; char c=getchar();while(c<'0' || c>'9'){if(c=='-') sign=-1; c=getchar();}while(c>='0' && c<='9'){x=x*10+c-'0'; c=getchar();}return x*sign;
}void Init()
{for(int i=0;i<=tot;++i) Last[i]=0; tot=0; ans=0; for(int i=0;i<=n;++i) Vis[i]=false;
}void AddEdge(int u,int v,int w)
{Edge[++tot].to=v; Edge[tot].len=w; Edge[tot].last=Last[u]; Last[u]=tot;
}void Read()
{n=getint();int u,v,w;for(int i=1;i<n;i++){u=getint(); v=getint(); w=getint();w%=3;AddEdge(u,v,w); AddEdge(v,u,w);}
}void GetRoot(int x,int father)
{int v;SonNum[x]=1; MaxNum[x]=1;for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; if(v==father || Vis[v]) continue;GetRoot(v,x);SonNum[x]+=SonNum[v];if(SonNum[v]>MaxNum[x]) MaxNum[x]=SonNum[x];}if(ss-SonNum[x]>MaxNum[x]) MaxNum[x]=ss-SonNum[x];if(rootx>MaxNum[x]) root=x,rootx=MaxNum[x];
}void GetDis(int x,int father,int dis)
{int v;Dis[++dlen]=dis;for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; if(v==father|| Vis[v]) continue;GetDis(v,x,dis+Edge[i].len);}
}ll Count(int x,int dis)
{ll ret=0;for(int i=0;i<=dlen;++i) Dis[i]=0;dlen=0;GetDis(x,0,dis);memset(Cnt,0,sizeof(Cnt));for(int i=1;i<=dlen;++i){++Cnt[Dis[i]%3];}ret=Cnt[1]*Cnt[2]*2+Cnt[0]*Cnt[0];return ret;
}void Solve(int x)
{int v;ans+=Count(x,0);Vis[x]=true;for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; if(Vis[v]) continue;ans-=Count(v,Edge[i].len);ss=SonNum[v]; rootx=INT_MAX; root=0;GetRoot(v,x);Solve(root);}
}void Work()
{rootx=INT_MAX; ss=n; root=0;GetRoot(1,0); Solve(root);
}ll gcd(ll x,ll y)
{return y==0?x:gcd(y,x%y);
}void Write()
{ll tmp=n*n;ll d=gcd(tmp,ans);printf("%lld/%lld",ans/d,tmp/d);}int main()
{Init();Read();Work();Write();return 0;
}
