[bzoj1468][poj1741]Tree[点分治]

可以说是点分治第一题，之前那道的点分治只是模模糊糊，做完这道题感觉清楚了很多，点分治可以理解为每次树的重心（这样会把数分为若干棵子树，子树大小为log级别），然后统计包含重心的整个子树的值减去各个子树的值，这样算出的就是与这个重心有关的情况的答案，比如这道题，求路径，那么就考虑在重心所在的子树中所有的路径减去不过重心的路径就是过重心的路径了。之前重心没找对...poj时间卡的紧就T了。。

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <cstdio>
  4 #include <cstdlib>
  5 #include <cstring>
  6 #include <cmath>
  7 #include <ctime>
  8 
  9 using namespace std;
 10 
 11 struct Edge
 12 {
 13     int    to,next,w;
 14 }e[210000];
 15 
 16 int    n,k,cnt,p[110000],Ans;
 17 int    Son[110000],f[110000],val[110000],depth[110000];
 18 bool    visited[110000];
 19 
 20 void    Add_edge(const int x,const int y,const int z)
 21 {
 22     e[++cnt].to=y;
 23     e[cnt].next=p[x];
 24     e[cnt].w=z;
 25     p[x]=cnt;
 26     return ;
 27 }
 28 
 29 void    Get_root(const int S,const int fa,const int tot,int & root)
 30 {
 31     Son[S]=1,f[S]=0;
 32     for(int i=p[S];i;i=e[i].next)
 33     {
 34         if(e[i].to==fa || visited[e[i].to])continue;
 35         Get_root(e[i].to,S,tot,root);
 36         Son[S]+=Son[e[i].to];
 37         f[S]=max(f[S],Son[e[i].to]);
 38     }
 39     f[S]=max(f[S],tot-Son[S]);
 40     if(f[S]<f[root])root=S;
 41     return ;
 42 }
 43 
 44 void    Get_depth(const int S,const int fa)
 45 {
 46     val[++val[0]]=depth[S];
 47     for(int i=p[S];i;i=e[i].next)
 48     {
 49         if(e[i].to==fa || visited[e[i].to])continue;
 50         depth[e[i].to]=depth[S]+e[i].w;
 51         Get_depth(e[i].to,S);
 52     }
 53     return ;
 54 }
 55 
 56 int    Calc(const int S,const int w)
 57 {
 58     depth[S]=w,val[0]=0;
 59     Get_depth(S,0);
 60     sort(val+1,val+val[0]+1);
 61     int    t=0,l,r;
 62     for(l=1,r=val[0];l<r;)
 63     {
 64         if(val[l]+val[r]<=k)t+=r-l,l++;
 65         else    r--;
 66     }
 67     return t;
 68 }
 69 
 70 void    TDC(const int S)
 71 {
 72     Ans+=Calc(S,0);
 73     visited[S]=true;
 74     for(int i=p[S];i;i=e[i].next)
 75     {
 76         if(visited[e[i].to])continue;
 77         Ans-=Calc(e[i].to,e[i].w);
 78         int root=0;
 79         Get_root(e[i].to,0,Son[e[i].to],root);
 80         TDC(root);
 81     }
 82     return ;
 83 }
 84 
 85 int main()
 86 {
 87     int    x,y,z,i,root;
 88 
 89     while(scanf("%d%d",&n,&k) && n && k)
 90     {
 91         root=0,memset(p,0,sizeof(p));cnt=0;
 92         memset(visited,0,sizeof(visited));
 93         Ans=0;
 94         for(i=1;i<n;++i)
 95         {
 96             scanf("%d%d%d",&x,&y,&z);
 97             Add_edge(x,y,z);
 98             Add_edge(y,x,z);
 99         }
100 
101         f[0]=0x3f3f3f3f;
102         Get_root(1,0,n,root);
103         TDC(root);
104 
105         printf("%d\n",Ans);
106     }
107 
108     return 0;
109 }

秒客网

[bzoj1468][poj1741]Tree[点分治]

相关文章