对于无根树，指定重心为根，考虑分别统计经过根的和不经过根的，在分别统计子树
1 const int Mn = 10000 + 10 , Me = 2 * 10000 + 10; 2 int hd[Mn],nxt[Me],to[Me],w[Me],cnt; 3 int size[Mn],dis[Mn],g[Mn],tot; 4 bool vis[Mn]; 5 int n,k; 6 inline void add(int x, int y, int z) 7 { 8 to[cnt] = y; 9 w[cnt] = z; 10 nxt[cnt] = hd[x]; 11 hd[x] = cnt++; 12 } 13 inline void dfs_dis(int x,int dist,int p) 14 { 15 dis[++tot] = dist; 16 for(int i = hd[x]; ~i; i = nxt[i]) 17 if(!vis[to[i]] && i != p) 18 dfs_dis(to[i],dist+w[i],i^1); 19 } 20 inline int find_root(int x,int p,int root) 21 { 22 int minx = n; 23 int ret(0); 24 for(int i = hd[x];~i; i = nxt[i]) 25 if(!vis[to[i]] && i != p) 26 { 27 int tmp = find_root(to[i],i^1,root); 28 if(g[tmp] < minx) 29 ret = tmp,minx = g[tmp]; 30 } 31 g[x] = max(g[x],size[root]-size[x]); 32 if(g[x] < minx) ret = x; 33 return ret; 34 } 35 inline void dfs_root(int x,int p) 36 { 37 size[x] = 1; 38 g[x] = 0; 39 for(int i = hd[x];~i; i = nxt[i]) 40 if(!vis[to[i]] && i != p) 41 { 42 dfs_root(to[i],i^1); 43 size[x] += size[to[i]]; 44 g[x] = max(g[x],size[to[i]]); 45 } 46 } 47 inline int get_root(int x) 48 { 49 dfs_root(x,-1); 50 return find_root(x,-1,x); 51 } 52 inline int calc(int x, int y) 53 { 54 tot = 0; 55 dfs_dis(x,y,-1); 56 sort(dis+1,dis+tot+1); 57 int j = tot; 58 int res(0); 59 for(int i = 1; i < j; i++) 60 { 61 while(dis[i] + dis[j] > k && i < j) j--; 62 res += j-i; 63 } 64 return res; 65 } 66 inline int dfs(int x) 67 { 68 int root = get_root(x); 69 vis[root] = true; 70 int res(0); 71 res += calc(root,0); 72 for(int i = hd[root]; ~i; i = nxt[i]) 73 if(!vis[to[i]]) 74 { 75 res -= calc(to[i],w[i]); 76 res += dfs(to[i]); 77 } 78 return res; 79 } 80 int main() 81 { 82 while(scanf("%d%d",&n,&k),n+k) 83 { 84 cnt = 0; 85 memset(hd,-1,sizeof hd); 86 memset(vis,false,sizeof vis); 87 for(int i = 1; i < n; i++) 88 { 89 int x,y,z; 90 scanf("%d%d%d",&x,&y,&z); 91 add(x,y,z); 92 add(y,x,z); 93 } 94 printf("%d ",dfs(1)); 95 } 96 }