首页 > 代码库 > BZOJ2152 聪聪可可 点分治
BZOJ2152 聪聪可可 点分治
题意:给定一棵树,求树中长度为三的倍数的路径条数
题解:定义c[i]为一颗子树中每个节点到根的距离%3等于i的路径数量,和poj1741一样,我们只需要找出只在一颗子树中的路径,就是c[1]*c[2]*2+c[0]*c[0]
#include <cstdio>#include <cstring>#include <cstdlib>#include <iostream>#include <algorithm>using namespace std;const int MAXN=20000+2;struct EDGE{ int u,w; EDGE *next; EDGE(){} EDGE(int _u,int _w,EDGE *_next):u(_u),w(_w),next(_next){}}mem[2*MAXN];struct NODE{ int c,m; EDGE *child;}node[MAXN];int N,cnt,ans,root,m,c[3];bool flag[MAXN];int gcd(int a,int b){ return !b?a:gcd(b,a%b);}void Insert(int u,int v,int w){ node[u].child=&(mem[cnt++]=EDGE(v,w,node[u].child));}void Find_Root(int u,int f){ node[u].c=1,node[u].m=0; for(EDGE *p=node[u].child;p;p=p->next) if(!flag[p->u] && p->u!=f){ Find_Root(p->u,u); node[u].c+=node[p->u].c,node[u].m=max(node[u].m,node[p->u].c); } node[u].m=max(node[u].m,m-node[u].c); if(node[u].m<node[root].m) root=u;}void Find_Node(int u,int f,int w){ c[w]++; for(EDGE *p=node[u].child;p;p=p->next) if(!flag[p->u] && p->u!=f) Find_Node(p->u,u,(w+p->w)%3);}int Calc(int u,int w){ c[0]=c[1]=c[2]=0; Find_Node(u,0,w%3); return c[2]*c[1]*2+c[0]*c[0];}void DFS(int u){ ans+=Calc(u,0),flag[u]=1; for(EDGE *p=node[root].child;p;p=p->next) if(!flag[p->u]){ ans-=Calc(p->u,p->w); m=node[p->u].c,root=0; Find_Root(p->u,0),DFS(root); }}int main(){ scanf("%d",&N); for(int i=1,u,v,w;i<N;i++){ scanf("%d %d %d",&u,&v,&w); Insert(u,v,w),Insert(v,u,w); } m=node[0].m=N; Find_Root(1,0),DFS(root); printf("%d/%d\n",ans/gcd(N*N,ans),N*N/gcd(N*N,ans)); return 0;}
BZOJ2152 聪聪可可 点分治
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。