首页 > 代码库 > BZOJ2152: 聪聪可可
BZOJ2152: 聪聪可可
2152: 聪聪可可
Time Limit: 3 Sec Memory Limit: 259 MBSubmit: 448 Solved: 236
[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)。
【数据规模】
对于100%的数据，n<=20000。
【样例说明】
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。
HINT
Source
树的分治
题解：
点分治，和poj的tree差不多。
这种统计路径的条数的问题，用点分治比较好。
代码：
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 20000+10014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26 int x=0,f=1;char ch=getchar();27 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29 return x*f;30 }31 struct edge{int go,next,w;}e[2*maxn];32 int tot,sum,k,root,head[maxn],s[maxn],f[maxn],deep[maxn],d[maxn];33 bool vis[maxn];34 ll ans=0,n,cnt[3];35 inline void insert(int x,int y,int z)36 {37 e[++tot].go=y;e[tot].next=head[x];e[tot].w=z;head[x]=tot;38 e[++tot].go=x;e[tot].next=head[y];e[tot].w=z;head[y]=tot;39 }40 void getroot(int x,int fa)41 {42 f[x]=-inf;s[x]=1;43 for(int i=head[x],y;i;i=e[i].next)44 if(!vis[y=e[i].go]&&y!=fa)45 {46 getroot(y,x);47 s[x]+=s[y];48 f[x]=max(f[x],s[y]);49 }50 f[x]=max(f[x],sum-s[x]);51 if(f[x]<f[root])root=x;52 }53 void getdeep(int x,int fa)54 {55 deep[++deep[0]]=d[x];56 for(int i=head[x],y;i;i=e[i].next)57 if(!vis[y=e[i].go]&&y!=fa)58 {59 d[y]=d[x]+e[i].w;60 getdeep(y,x);61 }62 }63 ll calc(int x,int now)64 {65 deep[0]=0;d[x]=now;66 getdeep(x,0);67 cnt[0]=cnt[1]=cnt[2]=0;68 for1(i,deep[0])cnt[deep[i]%3]++;69 return cnt[1]*cnt[2]*2+cnt[0]*cnt[0];70 }71 void work(int x)72 {73 vis[x]=1;74 ans+=calc(x,0);75 for(int i=head[x],y;i;i=e[i].next)76 if(!vis[y=e[i].go])77 {78 ans-=calc(y,e[i].w);79 sum=s[y];80 root=0;81 getroot(y,x);82 work(root);83 }84 }85 inline ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}86 int main()87 {88 freopen("input.txt","r",stdin);89 freopen("output.txt","w",stdout);90 n=read();91 for1(i,n-1){int x=read(),y=read(),z=read();insert(x,y,z);} 92 root=0;sum=n;93 f[0]=inf;94 getroot(1,0);95 work(root);96 ll tmp=n*n,t=gcd(ans,tmp);97 printf("%lld/%lld\n",ans/t,tmp/t);98 return 0;99 }
BZOJ2152: 聪聪可可
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。