Tree

Give a tree with n vertices,each edge has a length(positive integer less than 1001).
Define dist(u,v)=The min distance between node u and v.

Give an integer k,for every pair (u,v) of vertices is called valid if and only if dist(u,v) not exceed k.

Write a program that will count how many pairs which are valid for a given tree.

The input contains several test cases. The first line of each
test case contains two integers n, k. (n<=10000) The following n-1
lines each contains three integers u,v,l, which means there is an edge
between node u and v of length l.

The last test case is followed by two zeros.

For each test case output the answer on a single line.

5 4

1 2 3

1 3 1

1 4 2

3 5 1

0 0

8
树的点分治 参考了漆子超的论文 以及多位大佬的博客 

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 #include<map>

 #include<set>

 #include<vector>

 #include<cstdlib>

 #include<stack>

 #include<string>

 #define eps 0.000000001

 typedef long long ll;

 typedef unsigned long long LL;

 using namespace std;

 const int INF=0x3f3f3f3f;

 const int N=+;

 int son[N];

 int ans;

 int num;

 int p;

 int head[N];

 int vis[N];

 int minn;

 int root;

 int k;

 int dis[N];

 void init(){

     num=;

     memset(vis,,sizeof(vis));

     memset(head,-,sizeof(head));

 }

 struct node{

     int to,next,w;

 }edge[N];

 void add(int u,int v,int w){

     edge[num].to=v;

     edge[num].w=w;

     edge[num].next=head[u];

     head[u]=num++;

 }

 void getroot(int x,int y,int n){

     son[x]=;

     int maxx=;

     for(int i=head[x];i!=-;i=edge[i].next){

         int v=edge[i].to;

         if(v==y||vis[v])continue;

         getroot(v,x,n);

         son[x]=son[x]+son[v];

         maxx=max(maxx,son[v]);

     }

     maxx=max(maxx,n-son[x]);

     //cout<<maxx<<" "<<x<<endl;

     if(minn>maxx){

         minn=maxx;

         root=x;

     }

 }

 void getdeep(int x,int v0,int y){

     dis[p++]=y;

     for(int i=head[x];i!=-;i=edge[i].next){

         int v=edge[i].to;

         if(v==v0||vis[v])continue;

         getdeep(v,x,y+edge[i].w);

     }

 }

 int cal(int x,int y){

     int res=;

     p=;

     getdeep(x,,y);

     sort(dis,dis+p);

     int l=;

     int r=p-;

     while(l<r){

         if(dis[l]+dis[r]<=k){

             res=res+(r-l);

             l++;

         }

         else{

             r--;

         }

     }

     return res;

 }

 void work(int x){

     ans=ans+cal(x,);

     //cout<<cal(x,0)<<" ";

    // cout<<endl;

     vis[x]=;

     for(int i=head[x];i!=-;i=edge[i].next){

         int v=edge[i].to;

         if(vis[v]==){

             ans=ans-cal(v,edge[i].w);

             minn=INF;

             getroot(v,,son[v]);

             work(root);

         }

     }

 }

 int main(){

     int n;

     while(scanf("%d%d",&n,&k)!=EOF){

         if(n==&&k==)break;

         init();

         for(int i=;i<n-;i++){

             int u,v,w;

             scanf("%d%d%d",&u,&v,&w);

             add(u,v,w);

             add(v,u,w);

         }

         ans=;

         minn=INF;

         getroot(,-,n);

         //for(int i=1;i<=n;i++)cout<<son[i]<<" ";

        // cout<<endl;

        //cout<<root<<" "<<minn<<endl;

         work(root);

         cout<<ans<<endl;

     }

     return ;

 }