首页 > 代码库 > [BZOJ 2152]聪聪可可（点分治）
[BZOJ 2152]聪聪可可（点分治）
Description
聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画n个“点”，并用n-1条“边”把这n个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是3的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。
Solution
一道比较裸的点分
每次用t[i]记录到该点距离模3为i的点个数量
#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#define MAXN 20005#define INF 0x3f3f3f3fusing namespace std;int n,head[MAXN],siz[MAXN],maxv[MAXN],root=0,tot=0,num=0,cnt=0,t[3],p,q;bool vis[MAXN];int read(){ int x=0,f=1;char c=getchar(); 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;}struct Node{ int next,to,w;}Edges[MAXN*2];int gcd(int a,int b){return b?gcd(b,a%b):a;}void addedge(int u,int v,int w){ Edges[cnt].next=head[u]; head[u]=cnt; Edges[cnt].to=v; Edges[cnt++].w=w;}void getroot(int u,int f){ siz[u]=1,maxv[u]=0; for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(v==f||vis[v])continue; getroot(v,u); siz[u]+=siz[v],maxv[u]=max(maxv[u],siz[v]); } maxv[u]=max(maxv[u],tot-siz[u]); if(maxv[u]<maxv[root])root=u;}void getdeep(int u,int f,int d){ t[d]++; for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(v==f||vis[v])continue; getdeep(v,u,(d+Edges[i].w)%3); }}int calc(int u,int d){ memset(t,0,sizeof(t)); getdeep(u,0,d); return t[0]*t[0]+t[1]*t[2]*2;}void work(int u){ vis[u]=1;p+=calc(u,0); for(int i=head[u];~i;i=Edges[i].next) { int v=Edges[i].to; if(vis[v])continue; p-=calc(v,Edges[i].w%3); tot=siz[v],root=0; getroot(v,u),work(root); }}int main(){ memset(head,-1,sizeof(head)); n=read(); for(int i=1;i<n;i++) { int u=read(),v=read(),w=read(); addedge(u,v,w),addedge(v,u,w); } maxv[0]=INF,tot=n; p=0,q=n*n; getroot(1,0),work(1); int t=gcd(p,q); printf("%d/%d\n",p/t,q/t); return 0;}
[BZOJ 2152]聪聪可可（点分治）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。