Description

　　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. 

Input

　　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. 

Output

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

Sample Input

　5 4　1 2 3　1 3 1　1 4 2　3 5 1　0 0

Sample Output

　8

题解：

　　第一次写点分治感觉还好吧，对于一个子树先dfs预处理出sz(O(n))，然后dfs求出树的重心(O(n))，然后再分治下去(log)。

　　计算答案时会算重，比如两个点都属于当前重心的一个子树，这两个点是不会通过当前重心的，所以要容斥删去。（记得每次寻找重心要初始化）

　　怎么删，把重心的子节点再次计算减掉即可。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7 struct nd{ 8     int to,next,v; 9 }    e[20005];10 int head[10005],dep[10005],d[10005],mx[10005],sz[10005];11 bool vis[10005];12 int sum,ans,rt;13 int n,k,cnt;14 inline void insert(int u,int v,int w){15     e[++cnt].next=head[u];16     head[u]=cnt;17     e[cnt].to=v;18     e[cnt].v=w;19 }20 inline void findG(int now,int fa){21     mx[now]=0;22     for(int i=head[now];i;i=e[i].next){23         if(e[i].to==fa || vis[e[i].to])    continue;24         findG(e[i].to,now);25         mx[now]=max(mx[now],sz[e[i].to]);26     }27     mx[now]=max(mx[now],sum-sz[now]);28     if(mx[now]