題目描述
聰聰和可可是兄弟倆,他們倆經常為了一些瑣事打起來,例如家中隻剩下最後一根冰棍而兩人都想吃、兩個人都想玩兒電腦(可是他們家隻有一台電腦)……遇到這種問題,一般情況下石頭剪刀布就好了,可是他們已經玩兒膩了這種低智商的遊戲。
他們的爸爸快被他們的争吵煩死了,是以他發明了一個新遊戲:由爸爸在紙上畫n個“點”,并用n-1條“邊”把這n個“點”恰好連通(其實這就是一棵樹)。并且每條“邊”上都有一個數。接下來由聰聰和可可分别随即選一個點(當然他們選點時是看不到這棵樹的),如果兩個點之間所有邊上數的和加起來恰好是3的倍數,則判聰聰赢,否則可可赢。
聰聰非常愛思考問題,在每次遊戲後都會仔細研究這棵樹,希望知道對于這張圖自己的獲勝機率是多少。現請你幫忙求出這個值以驗證聰聰的答案是否正确。
輸入輸出格式
輸入格式:
輸入的第1行包含1個正整數n。後面n-1行,每行3個整數x、y、w,表示x号點和y号點之間有一條邊,上面的數是w。
輸出格式:
以即約分數形式輸出這個機率(即“a/b”的形式,其中a和b必須互質。如果機率為1,輸出“1/1”)。
輸入輸出樣例
輸入樣例#1:
5
1 2 1
1 3 2
1 4 1
2 5 3
輸出樣例#1:
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。
解題思路
先周遊一遍找出樹的重心,把重心作為根,然後dis數組(别的部落格大部分叫d)記錄沒統計過的兒子到達目前樹根的邊權和,t[0]、t[1]、t[2]分别記錄dis模3之後餘數為0、1、2的點的個數,乘法原理得到過目前根的路徑的權值模三為零的點對數為$t[0]*t[0]+t[1]*t[2]*2$。然後對目前根的每棵子樹做相同的操作,不過給子樹找重心前還要去重。比如點對a到b路徑為a->r1->r2->r1->b,當r2做根時a、b就統計了一遍,操作r2的子樹r1時,如果r1->r2權值能被3整除,那麼a->r1->b的權值和依然能被3整除,就會導緻a、b重複計算,是以要去重。(要是有時間畫個圖就好懂了)
源代碼
#include<cstdio>
#include<algorithm>
int n;
struct Edge{
int next,to,w;
}e[40010];
int head[40010]={0},cnt=1;
void add(int u,int v,int w)
{
e[cnt]={head[u],v,w};
head[u]=cnt++;
e[cnt]={head[v],u,w};
head[v]=cnt++;
}
int root,sum,ans=0;
int t[3]={0};
int num_to[20010]={0},max_son[20010]={0},dis[20010]={0};
bool vis[20010]={0};
int getroot(int u,int fa)
{
num_to[u]=1;max_son[u]=0;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(vis[v]||v==fa) continue;
getroot(v,u);
num_to[u]+=num_to[v];
max_son[u]=std::max(max_son[u],num_to[v]);
}
max_son[u]=std::max(max_son[u],sum-num_to[u]);
if(max_son[u]<max_son[root]) root=u;
}
void getdis(int u,int fa)
{
t[dis[u]]++;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(vis[v]||v==fa) continue;
dis[v]=(dis[u]+e[i].w)%3;
getdis(v,u);
}
}
int cal(int u,int D)
{
dis[u]=D%3;
t[0]=t[1]=t[2]=0;
getdis(u,0);
return t[0]*t[0]+t[1]*t[2]*2;
}
void work(int u)
{
ans+=cal(u,0);
vis[u]=1;
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(vis[v]) continue;
ans-=cal(v,e[i].w);
root=0;
sum=num_to[v];
getroot(v,0);
work(root);
}
}
int main()
{
scanf("%d",&n);
for(int i=1,u,v,w;i<n;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u,v,w%3);
}
max_son[0]=sum=n;
getroot(1,0);
work(root);
int m=n*n;
int g=std::__gcd(m,ans);//algorithm裡自帶的gcd
printf("%d/%d\n",ans/g,m/g);
return 0;
}