2152: 聪聪可可
Time Limit: 3 Sec Memory Limit: 259 MBSubmit: 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
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。
树的点分治裸题，就不多说了，总结几个易错点：分治要从重心分，不要求完重心就不管了。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[
3];
qword gcd(qword a,qword b)
{
return (a%b==
0)?b:gcd(b,a%
b);
}
struct Edge
{
int np,val;
int state;
int rec_size;
Edge *next,*
neg;
}E[MAXE],*
V[MAXV];
int tope=-
1;
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=
0;
int t,sum=
1;
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[0]=
1;lst[
1]=lst[
2]=
0;
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[(0+ne->val)%
3]+=at[
0];
lst[(1+ne->val)%
3]+=at[
1];
lst[(2+ne->val)%
3]+=at[
2];
}
}
qword solve(int now,
int tree_size)
{
if (tree_size==
1)
{
return 0;
}
Edge *
ne;
int core;
qword ret=
0;
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[0]=res[
1]=res[
2]=
0;
for (ne=V[core];ne;ne=ne->
next)
{
if (ne->state!=core)
continue;
at2[0]=
0;at2[
1]=at2[
2]=
0;
dfs(at,ne->
np,core);
at2[(0+ne->val)%
3]+=at[
0];
at2[(1+ne->val)%
3]+=at[
1];
at2[(2+ne->val)%
3]+=at[
2];
ret+=res[
0]*at2[
0] + res[
1]*at2[
2] + res[
2]*at2[
1];
ret+=at2[
0];
res[0]+=at2[
0];res[
1]+=at2[
1];res[
2]+=at2[
2];
}
for (ne=V[core];ne;ne=ne->
next)
{
if (ne->state==
core)
{
ne->state=ne->neg->state=
0;
}
}
return ret;
}
int main()
{
freopen("input.txt",
"r",stdin);
int n;
int i,j,k,x,y,z;
scanf("%d",&
n);
for (i=
0;i<n-
1;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(
1,n)*
2+
n;
qword b=n*
n;
qword c=
gcd(a,b);
//cout<<a<<endl;
printf(LL
"/" LL
"\n",a/c,b/
c);
}
转载于:https://www.cnblogs.com/mhy12345/p/4055378.html
