给定一棵树，边上有权值，要统计有多少对点路径的权值和<=k
分治算法在树的路径中的应用 这个论文里面有分析。
任意两点的路径，要么过根结点，要么在子树中。如果在子树中，那么只要递归处理就行了。
所以只要统计过根结点的对数。
所以只要算出任意结点到根结点的距离，用dist数组存下来，然后排序dist数组，就可以在O(n)的时间内算出有多少对点满足条件，具体见counts函数
但是counter函数计算时，会把路径都在子树中的情况也给加进来，所以需要再对相应的子树进行counts函数，然后减去。
然后在递归计算路径经过孩子结点的情况。
但是这样子的算法是会退化的，因为树可能是一条链。
所以就需要用到重心了。 因为重心具有的一个性质是删掉重心后，可以使得剩下的分支中，最大的最小。
所以在算出所有经过u的点对之后，递归计算v这个子树时，相当于计算一棵全新的树，所以只要找到这棵树的重心，继续计算就行了。
因为结点数可以每次都减少为原来的一般，所以层数只有logn层， 每层统计时，排序要nlogn，所以总的时间复杂度是n*logn*logn
#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <bitset>
#include <algorithm>
#include <iostream>
#include <string>
#include <functional>
const int INF = << ;
typedef __int64 LL;
/*
dist(u,v)为u，v两点路径上所有边的权和
如果dist(u,v)<=k，那么称(a,b)为合法点对
求合法点对的个数
N<=10000, k<=10^9 depth(i) + depth(j) <=k 且belong(i)!=belong(j) 我的问题是？ 分治的时候，如何将树两边的点合起来？？？
*/
const int N = + ;
struct Node
{
int to, next, dis;
}g[N];
int head[N], e;
int n, k, ans;
int size[N];
int mins, total, root;
int dist[N], p;
int vis[N];
int cnt[N];
void addEdge(int u, int v, int dis)
{
g[e].to = v;
g[e].dis = dis;
g[e].next = head[u];
head[u] = e++;
} void dfsRoot(int u, int f)
{
size[u] = ;
int mxs = ;
for (int i = head[u]; i != -; i = g[i].next)
{
int v = g[i].to;
if (v == f || vis[v]) continue;
dfsRoot(v, u);
size[u] += size[v];
mxs = std::max(mxs, size[v]);
}
//下面是找重心的代码
if(mxs < total - size[u])
mxs = total - size[u];
if (mxs < mins)
mins = mxs, root = u;
} void getDis(int u, int f, int dis)
{
dist[p++] = dis;//遍历没有访问过的点，将到根结点的距离存下来
for (int i = head[u]; i != -; i = g[i].next)
{
int v = g[i].to;
if (v == f || vis[v]) continue;
getDis(v, u, dis + g[i].dis);
}
}
int counts(int u, int dis)
{
int ret = ;
p = ;
getDis(u, , dis);//得到dist数组
std::sort(dist, dist + p);//每访问一个重心都要排序一次，所以是n*logn*logn
int l = , r = p - ;
while (l < r)
{
//如果dist[l]+dist[r]<=k ，那么dist[l]+任意的点都是可行的
if (dist[l] + dist[r] <= k)
{
ret += (r - l);
l++;//判断下一个l
}
else//如果这个r不行，那么这个r与谁结合都是不行的
r--;
}
return ret;
} void go(int u)
{
//total存的是子树所有结点
mins = INF, total = size[u] ? size[u] : n;
dfsRoot(u, -);//找到重心
u = root;
vis[u] = true;
cnt[u] = ;
cnt[u] += counts(u, );//统计过这个点的点对
//但是会发生一个错误就是可能统计了位于同一棵子树的点
for (int i = head[u]; i != -; i = g[i].next)
{
int v = g[i].to;
if (vis[v]) continue;
cnt[u] -= counts(v, g[i].dis);//所有要减去位于同一棵子树的点
go(v);
}
}
int main()
{ while(scanf("%d%d", &n, &k),n+k)
{
int u, v, dis;
e = ;
memset(head, -, sizeof(head));
for (int i = ;i < n;++i)
{
scanf("%d%d%d", &u, &v, &dis);
addEdge(u, v, dis); addEdge(v, u, dis);
}
ans = ;
size[] = ;
memset(vis, , sizeof(vis));
go();
for (int i = ;i <= n;++i)
ans += cnt[i];
printf("%d\n", ans);
}
return ;
}