点分治练习——BZOJ 2152

做的第二道点分治的题目,比较裸,算是模板题吧(感觉比之前那题还简单点。

 

题目:BZOJ 2152 聪聪可可

题目大意:给出一棵树,求树上两点间长度为3的倍数(0也算)的路径数。

解题思路:

基本和POJ1741一样

    2.不过重心,在重心的子树中

情况二可通过分治转化为情况1。

通过dfs求出每个点到重心的距离%3,将余数是1的和是2的配对,余数是0的两两配对,得出路径数。

同样的,注意去重。

    代码:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 struct edge{
 7     int w,to,next;
 8 }e[40100];
 9 
10 int head[20010],s[20010],f[20010],d[20010],t[3],ans,size;
11 bool b[20010];
12 int n,i,j,v,w,x,y,ne=0,root;
13 
14 void add(int a,int b,int c){
15     e[++ne].to=b; e[ne].w=c; e[ne].next=head[a]; head[a]=ne;
16 }
17 
18 void getroot(int k,int fa){
19     int v,i;
20     s[k]=1;f[k]=0;
21     for(i=head[k];i!=-1;i=e[i].next){
22         v=e[i].to;
23         if(v!=fa&&!b[v]){
24             getroot(v,k);
25             s[k]+=s[v];
26             f[k]=max(f[k],s[v]);
27         }
28     }
29     f[k]=max(f[k],size-s[k]);
30     if(f[k]<f[root])root=k;
31 }
32 
33 void getdis(int k,int fa){
34     int v,i;
35     t[d[k]]++;//将对应余数的数目+1;
36     for(i=head[k];i!=-1;i=e[i].next){
37         v=e[i].to;
38         if (v!=fa&&!b[v]){
39             d[v]=(d[k]+e[i].w)%3;
40             getdis(v,k);
41         }
42     }
43 }
44 
45 int clac(int k,int init){
46     t[0]=t[1]=t[2]=0;//余数清0
47     d[k]=init%3;
48     getdis(k,0);//计算深度
49     return (t[1]*t[2]*2+t[0]*t[0]);//计算路径数
50 }
51 
52 void work(int k){
53     int i,v;
54     ans+=clac(k,0);//更新ans
55     b[k]=true;
56     for(i=head[k];i!=-1;i=e[i].next){
57         v=e[i].to;
58         if(!b[v]){
59             ans-=clac(v,e[i].w);//去重
60             f[0]=size=s[v];
61             root=0;
62             getroot(v,0);//更新重心
63             work(root);//求解子树
64         }
65     }
66 }
67 
68 int gcd(int a,int b){
69     if(b==0) return a;
70     return gcd(b,a%b);
71 }
72 
73 int main(){
74     ans=root=0;
75     memset(head,-1,sizeof(head));
76     memset(b,0,sizeof(b));
77     scanf("%d",&n);
78     for(i=1;i<n;i++){
79         scanf("%d%d%d",&x,&y,&w);
80         w%=3;
81         add(x,y,w);
82         add(y,x,w);//连双向边
83     }
84     f[0]=size=n;
85     getroot(1,0);//求重心
86     work(root);
87     int tmp=gcd(ans,n*n);
88     printf("%d/%d
",ans/tmp,n*n/tmp);
89 }
【推广】 免费学中医,健康全家人
原文地址:https://www.cnblogs.com/y-m-y/p/5779829.html