2152: 聪聪可可
Time Limit: 3 Sec Memory Limit: 259 MB
Submit: 485 Solved: 251
[Submit][Status]
Description
聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画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
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)。
【样例说明】
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。
树的点分治裸题，就不多说了，总结几个易错点：分治要从重心分，不要求完重心就不管了。dfs搜索时要避免走过已被分割的边。long long输出用lld
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 21000
#define MAXV MAXN
#define MAXE MAXV*2
#define INF 0x3f3f3f3f
#define LL "%lld"
typedef long long qword;
typedef int aaa[];
qword gcd(qword a,qword b)
{
return (a%b==)?b:gcd(b,a%b);
}
struct Edge
{
int np,val;
int state;
int rec_size;
Edge *next,*neg;
}E[MAXE],*V[MAXV];
int tope=-;
void addedge(int x,int y,int z)
{
E[++tope].np=y;
E[tope].val=z;
E[tope].next=V[x];
V[x]=&E[tope];
}
int bst_core,core_size;
int siz[MAXN];
int fa[MAXN];
int get_core(int now,int tree_size,int f)
{
Edge *ne;
int mxson=;
int t,sum=;
fa[now]=f;
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==f || ne->state)continue;
t=get_core(ne->np,tree_size,now);
sum+=t;
siz[ne->np]=t;
mxson=max(mxson,t);
}
mxson=max(mxson,tree_size-sum);
if (core_size>mxson)
{
core_size=mxson;
bst_core=now;
}
return sum;
}
void dfs(aaa& lst,int now,int f)
{
Edge *ne;
aaa at,ret;
lst[]=;lst[]=lst[]=;
for (ne=V[now];ne;ne=ne->next)
{
if (ne->np==f || ne->state)continue;//Make sure searching in correct area
dfs(at,ne->np,now);
lst[(+ne->val)%]+=at[];
lst[(+ne->val)%]+=at[];
lst[(+ne->val)%]+=at[];
}
} qword solve(int now,int tree_size)
{
if (tree_size==)
{
return ;
}
Edge *ne;
int core;
qword ret=;
core_size=INF;
int t=get_core(now,tree_size,now);
core=bst_core;
for (ne=V[core];ne;ne=ne->next)
{
if (!ne->state)
{
ne->state=core;
ne->neg->state=core;//This cannot be "now"
ne->rec_size=ne->np==fa[core]?t-siz[core]:siz[ne->np];
}
}
for (ne=V[core];ne;ne=ne->next)
{
if (ne->state!=core)continue;
ret+=solve(ne->np,ne->rec_size);
}
aaa at,at2,res;
res[]=res[]=res[]=;
for (ne=V[core];ne;ne=ne->next)
{
if (ne->state!=core)continue;
at2[]=;at2[]=at2[]=;
dfs(at,ne->np,core);
at2[(+ne->val)%]+=at[];
at2[(+ne->val)%]+=at[];
at2[(+ne->val)%]+=at[]; ret+=res[]*at2[] + res[]*at2[] + res[]*at2[];
ret+=at2[];
res[]+=at2[];res[]+=at2[];res[]+=at2[];
}
for (ne=V[core];ne;ne=ne->next)
{
if (ne->state==core)
{
ne->state=ne->neg->state=;
}
}
return ret;
}
int main()
{
freopen("input.txt","r",stdin);
int n;
int i,j,k,x,y,z;
scanf("%d",&n);
for (i=;i<n-;i++)
{
scanf("%d%d%d",&x,&y,&z);
addedge(x,y,z);
addedge(y,x,z);
V[x]->neg=V[y];
V[y]->neg=V[x];
}
qword a=solve(,n)*+n;
qword b=n*n;
qword c=gcd(a,b);
//cout<<a<<endl;
printf(LL "/" LL "\n",a/c,b/c);
}