首页 > 代码库 > bzoj 2152: 聪聪可可 树的点分治
bzoj 2152: 聪聪可可 树的点分治
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
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。
树的点分治裸题，就不多说了，总结几个易错点：分治要从重心分，不要求完重心就不管了。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);}
bzoj 2152: 聪聪可可 树的点分治
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。