首页 > 代码库 > 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;}
View Code

 

BZOJ2152 聪聪可可 点分治