poj1741（树的点分治）

题目连接：POJ - 1741
看了好长时间才明白了点......
网上讲解很多但感觉都不够详细。。。大概是太弱了吧-_-||
学通了再回来写详解。。。
  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<algorithm>
  5 #define LL long long
  6 using namespace std;
  7 const int N=1e5+10;
  8 const int inf=1e9+10;
  9 int n,k;
 10 int rt,ans,sumnode,siz[N],vis[N],d[N];
 11 int dep[N]; //路径长度//dep[0]为子节点个数
 12 int f[N]; //重心
 13 struct edge
 14 {
 15     int v,w,nex;
 16 }e[N*2];
 17 int head[N];
 18 int cnt;
 19 void add(int u,int v,int w)
 20 {
 21     e[cnt].v=v;
 22     e[cnt].w=w;
 23     e[cnt].nex=head[u];
 24     head[u]=cnt++;
 25 }
 26 void getrt(int u,int fa) //找重心
 27 {
 28     siz[u]=1;
 29     f[u]=0;
 30     for(int i=head[u];i!=-1;i=e[i].nex)
 31     {
 32         int v=e[i].v;
 33         if(v==fa||vis[v]) continue;
 34         getrt(v,u);
 35         siz[u]+=siz[v];
 36         f[u]=max(f[u],siz[v]);
 37     }
 38     f[u]=max(sumnode-siz[u],f[u]);
 39     if(f[u]<f[rt]) rt=u;
 40 }
 41 
 42 void getdep(int u,int fa)  //获取子树所有节点与根的距离
 43 {
 44     dep[++dep[0]]=d[u];
 45     for(int i=head[u];i!=-1;i=e[i].nex)
 46     {
 47         int v=e[i].v;
 48         if(v==fa||vis[v]) continue;
 49         d[v]=d[u]+e[i].w;
 50         getdep(v,u);
 51     }
 52 }
 53 
 54 int cal(int u,int now) //计算当前以重心u为根的子树下所有情况的答案
 55 {
 56     d[u]=now;
 57     dep[0]=0;
 58     getdep(u,0);
 59     sort(dep+1,dep+dep[0]+1);
 60     int all=0;
 61     for(int l=1,r=dep[0];l<r;)
 62     {
 63         if(dep[l]+dep[r]<=k) {all+=r-l;l++;}
 64         else r--;
 65     }
 66     return all;
 67 }
 68 
 69 void work(int u) //以u为重心计算
 70 {
 71     vis[u]=1;
 72     ans+=cal(u,0);
 73     for(int i=head[u];i!=-1;i=e[i].nex)
 74     {
 75         int v=e[i].v;
 76         if(vis[v]) continue;
 77         ans-=cal(v,e[i].w);
 78         sumnode=siz[v];
 79         rt=0;
 80         getrt(v,u);
 81         work(rt);
 82     }
 83 }
 84 int u,v,w;
 85 int main()
 86 {
 87     while(scanf("%d%d",&n,&k)!=EOF)
 88     {
 89         if(!n&&!k) break;
 90         memset(head,-1,sizeof(head));
 91         memset(vis,0,sizeof(vis));
 92         cnt=0;
 93         for(int i=0;i<n-1;i++)
 94         {
 95             scanf("%d%d%d",&u,&v,&w);
 96             add(u,v,w);
 97             add(v,u,w);
 98         }
 99         rt=ans=0;
100         sumnode=n;
101         f[0]=inf;
102         getrt(1,0);
103         work(rt);
104         printf("%d
",ans);
105     }
106 }