首页 > 代码库 > [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]聪聪可可(点分治)