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

又一道点分治膜版题
我果然是只会做膜版啊
还是贴上vector造图的代码吧
虽然它RE了
用数组膜你邻接表AC
我也很迷啊

好好好一个小时后的我发现自己一个小时前太sb了
居然忘了复原vector G了

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<vector>

 using namespace std;

 inline int read(){

     char ch;

     int re=;

     bool flag=;

     while((ch=getchar())!='-'&&(ch<''||ch>''));

     ch=='-'?flag=:re=ch-'';

     while((ch=getchar())>=''&&ch<='')  re=re*+ch-'';

     return flag?-re:re;

 }

 struct edge{

     int to,w;

     edge(int to=,int w=):

         to(to),w(w){}

 };

 const int maxn=;

 vector<edge> G[maxn];

 int son[maxn],F[maxn];

 int d[maxn],deep[maxn];

 bool vis[maxn];

 int sum,ans,root;

 int n,K;

 inline void add_edge(int from,int to,int w){

     G[from].push_back(edge(to,w));

     G[to].push_back(edge(from,w));

 }

 bool init(){

     n=read();

     if(!n)  return ;

     memset(G,,sizeof G);

     memset(vis,,sizeof vis);

     K=read();

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

         int from=read(),to=read(),w=read();

         add_edge(from,to,w);

     }

     return ;

 }

 void getroot(int x,int fa){

     son[x]=;

     F[x]=;

     int dd=G[x].size();

     for(int i=;i<dd;i++){

         edge &e=G[x][i];

         if(e.to!=fa&&!vis[e.to]){

             getroot(e.to,x);

             son[x]+=son[e.to];

             F[x]=max(F[x],son[e.to]);

         }

     }

     F[x]=max(F[x],sum-son[x]);

     if(F[x]<F[root])  root=x;

 }

 void getdeep(int x,int fa){

     deep[++deep[]]=d[x];

     int dd=G[x].size();

     for(int i=;i<dd;i++){

         edge &e=G[x][i];

         if(e.to!=fa&&!vis[e.to]){

             d[e.to]=d[x]+e.w;

             getdeep(e.to,x);

         }

     }

 }

 int calc(int x,int now){

     d[x]=now;

     deep[]=;

     getdeep(x,);

     sort(deep+,deep+deep[]+);

     int t=;

     for(int l=,r=deep[];l<r;){

         if(deep[l]+deep[r]<=K){

             t+=r-l;

             l++;

         }

         else  r--;

     }

     return t;

 }

 void work(int x){

     ans+=calc(x,);

     vis[x]=;

     int dd=G[x].size();

     for(int i=;i<dd;i++){

         edge &e=G[x][i];

         if(!vis[e.to]){

             ans-=calc(e.to,e.w);

             sum=son[e.to];

             root=;

             getroot(e.to,root);

             work(root);

         }

     }

 }

 void solve(){

     sum=F[root=]=n;

     ans=;

     getroot(,);

     work(root);

     printf("%d\n",ans);

 }

 int main(){

     //freopen("temp.in","r",stdin);

     while(init())

         solve();

     return ;

 }

他说你任何为人称道的美丽  不及他第一次遇见你