点分治第一题
这题我们考虑点分治
首先我们需要找到树的重心
然后做一遍
然后分成左右两块继续做，每一块重复上面的操作
具体的，我们每次计算每个点到重心的距离
然后放到一个数组里，再将距离和小于k的算进去
但是有可能重复统计了子树里面的数值
所以点分治的时候再减一下就好了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int n,k,h[10005],en,mx[10005],siz[10005],ans,root,val,vis[10005],temp[10005],cnt;
struct Edge{
int b,v,next;
}e[20005];
void AddEdge(int sa,int sb,int sc){
e[++en].b=sb;
e[en].v=sc;
e[en].next=h[sa];
h[sa]=en;
}
void DfsSiz(int u,int fa){
siz[u]=1;
mx[u]=0;
for(int i=h[u];i;i=e[i].next){
int v=e[i].b;
if(v!=fa && !vis[v]){
DfsSiz(v,u);
siz[u]+=siz[v];
mx[u]=max(mx[u],siz[v]);
}
}
}
void DfsRoot(int point,int u,int fa){
mx[u]=max(mx[u],siz[point]-siz[u]);
if(val>mx[u]){val=mx[u];root=u;}
for(int i=h[u];i;i=e[i].next){
int v=e[i].b;
if(v!=fa && !vis[v])DfsRoot(point,v,u);
}
}
void GetDist(int u,int fa,int val){
temp[++cnt]=val;
for(int i=h[u];i;i=e[i].next){
int v=e[i].b;
if(v!=fa && !vis[v])GetDist(v,u,val+e[i].v);
}
}
int Cal(int u,int val){
cnt=0;
int now=0;
GetDist(u,u,val);
sort(temp+1,temp+cnt+1);
int i=1,j=cnt;
while(i<j){
while(temp[i]+temp[j]>k && i<j)j--;
now+=j-i;
i++;
}
return now;
}
void Dfs(int u){
val=2100000000;
DfsSiz(u,u);
DfsRoot(u,u,0);
ans+=Cal(root,0);
vis[root]=1;
for(int i=h[root];i;i=e[i].next){
int v=e[i].b;
if(!vis[v]){
ans-=Cal(v,e[i].v);
Dfs(v);
}
}
}
int main(){
freopen("1741.in","r",stdin);
freopen("1741.out","w",stdout);
while(scanf("%d %d",&n,&k),n|k){
memset(h,0,sizeof(h));
memset(vis,0,sizeof(vis));
ans=en=0;
for(int i=1;i<n;i++){
int sa,sb,sc;
scanf("%d %d %d",&sa,&sb,&sc);
AddEdge(sa,sb,sc);
AddEdge(sb,sa,sc);
}
Dfs(1);
printf("%d\n",ans);
}
return 0;
}
