点分治模板

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #define inf 0x7fffffff
 6 using namespace std;
 7 int read()
 8 {
 9     int x=0,f=1;char ch=getchar();
10     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
11     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
12     return x*f;
13 }
14 int n,K,cnt,sum,ans,root;
15 int head[10005],deep[10005],d[10005],f[10005],son[10005];
16 bool vis[10005];
17 struct data{int to,next,v;}e[20005];
18 void ins(int u,int v,int w)
19 {e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;}
20 void insert(int u,int v,int w)
21 {ins(u,v,w);ins(v,u,w);}
22 void getroot(int x,int fa)
23 {
24     son[x]=1;f[x]=0;
25     for(int i=head[x];i;i=e[i].next)
26     {
27         if(e[i].to==fa||vis[e[i].to])continue;
28         getroot(e[i].to,x);
29         son[x]+=son[e[i].to];
30         f[x]=max(f[x],son[e[i].to]);
31     }
32     f[x]=max(f[x],sum-son[x]);
33     if(f[x]<f[root])root=x;
34 }
35 void getdeep(int x,int fa)
36 {
37     deep[++deep[0]]=d[x];
38     for(int i=head[x];i;i=e[i].next)
39     {
40         if(e[i].to==fa||vis[e[i].to])continue;
41         d[e[i].to]=d[x]+e[i].v;
42         getdeep(e[i].to,x);
43     }
44 }
45 int cal(int x,int now)
46 {
47     d[x]=now;deep[0]=0;
48     getdeep(x,0);
49     sort(deep+1,deep+deep[0]+1);
50     int t=0,l,r;
51     for(l=1,r=deep[0];l<r;)
52     {
53         if(deep[l]+deep[r]<=K){t+=r-l;l++;}
54         else r--;
55     }
56     return t;
57 }
58 void work(int x)
59 {
60     ans+=cal(x,0);
61     vis[x]=1;
62     for(int i=head[x];i;i=e[i].next)
63     {
64         if(vis[e[i].to])continue;
65         ans-=cal(e[i].to,e[i].v);
66         sum=son[e[i].to];
67         root=0;
68         getroot(e[i].to,root);
69         work(root);
70     }
71 }
72 int main()
73 {
74     while(1)
75     {
76         ans=0;root=0;cnt=0;
77         memset(vis,0,sizeof(vis));
78         memset(head,0,sizeof(head));
79         n=read();K=read();
80         if(n==0)break;
81         for(int i=1;i<n;i++)
82          {
83             int u=read(),v=read(),w=read();
84             insert(u,v,w);
85         }
86         sum=n;f[0]=inf;
87          getroot(1,0);
88         work(root);
89         printf("%d
",ans);
90     }
91     return 0;
92 }