首页 > 代码库 > BZOJ 2152: 聪聪可可 [点分治]
BZOJ 2152: 聪聪可可 [点分治]
2152: 聪聪可可
Time Limit: 3 Sec Memory Limit: 259 MBSubmit: 2424 Solved: 1277
[Submit][Status][Discuss]
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。
模板题
考虑经过一个点的路径，cou[i]表示深度%3==i的点的个数，cou[0]*cou[0]+cou[1]*cou[2]*2，然后减去同一棵子树里的
注意要设置sum啊要设置sum啊要设置sum啊要设置sum啊要设置sum啊要设置sum啊要设置sum啊要设置sum啊要设置sum啊
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>using namespace std;const int N=2e4+5,INF=1e9;int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();} return x*f;}int n,u,v,w;struct edge{ int v,w,ne;}e[N<<1];int h[N],cnt;inline void ins(int u,int v,int w){ cnt++; e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt; cnt++; e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;}int size[N],f[N],rt,vis[N],sum;void dfsRt(int u,int fa){ size[u]=1;f[u]=0; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(vis[v]||v==fa) continue; dfsRt(v,u); size[u]+=size[v]; f[u]=max(f[u],size[v]); } f[u]=max(f[u],sum-size[u]); if(f[u]<f[rt]) rt=u;}int deep[N],cou[4];void dfsDeep(int u,int fa){ cou[deep[u]]++; for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(vis[v]||v==fa) continue; deep[v]=(deep[u]+e[i].w)%3; dfsDeep(v,u); }}int cal(int u,int now){ deep[u]=now%3; memset(cou,0,sizeof(cou)); dfsDeep(u,0); return cou[0]*cou[0]+cou[1]*cou[2]*2;}int ans;void dfsSol(int u){//printf("sol %d\n",u); vis[u]=1; ans+=cal(u,0); for(int i=h[u];i;i=e[i].ne){ int v=e[i].v; if(vis[v]) continue; ans-=cal(v,e[i].w); sum=size[v]; rt=0;dfsRt(v,0);v=rt; dfsSol(v); }}inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}int main(){ //freopen("in.txt","r",stdin); n=read(); for(int i=1;i<n;i++) u=read(),v=read(),w=read(),ins(u,v,w); sum=n; f[0]=INF; rt=0;dfsRt(1,0); dfsSol(rt); int g=gcd(ans,n*n); printf("%d/%d",ans/g,n*n/g);}
BZOJ 2152: 聪聪可可 [点分治]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。