题目地址：

https://www.acwing.com/problem/content/254/

给定一个有 $N$ 个点（编号 $0, 1, \dots, N ? 1$ ）的树，每条边都有一个权值（不超过 $1000$ ）。树上两个节点 $x$ 与 $y$ 之间的路径长度就是路径上各条边的权值之和。求长度不超过 $K$ 的路径有多少条。

输入格式：
输入包含多组测试用例。
每组测试用例的第一行包含两个整数 $N$ 和 $K$ 。
接下来 $N ? 1$ 行，每行包含三个整数 $u, v, l$ ，表示节点 $u$ 与 $v$ 之间存在一条边，且边的权值为 $l$ 。
当输入用例 $N = 0 ， K = 0$ 时，表示输入终止，且该用例无需处理。

输出格式：
每个测试用例输出一个结果。每个结果占一行。

数据范围：
$1≤N≤10^4$
$1≤K≤5×10^6$
$0≤l≤10^3$

思路是分治。假设一开始我们随便选择一个顶点 $u$ 为树根，那么所有的路径可以分为三类：
1、完全在 $u$ 的某一棵子树里，这个可以递归求解；
2、路径的两个端点一个在子树里，另一个是树根，这个可以通过DFS求解每个点到树根的路径来解决；
3、路径的两个端点在不同子树里，这个可以先DFS求解每个点到树根的距离，然后在这个距离数组里求解和小于等于 $K$ 的数对有多少个。但是这个会将两个顶点在同一棵子树里的非法情况包括进去，我们可以对每个子树再求一次和小于等于 $K$ 的数对，然后将这个情况扣除即可。在一个数组里求和小于等于 $K$ 的数对个数，可以先排序，然后用双指针。

分治的每一层的时间大概是 $O(n\log n)$ ，如果递归层数过多，算法会退化到 $O(n^2\log n)$ ，所以我们为了递归层数尽量少，需要使得每次选树根的时候，子树大小尽量均衡，于是我们想到可以每次选重心作为树根（当然我们只需要该点的最大子树节点个数小于等于总点数一半即可，这样每次递归下去一层，最大子树节点个数就减半，从而达到递归 $O(\log n)$ 层的效果，不一定非要选择重心。不妨就将满足条件的点统称为“重心”）。求解树根，可以先DFS求树的节点个数，然后再DFS暴力枚举解决。

代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e4 + 10, M = N << 1;
int n, m;
int h[N], e[M], w[M], ne[M], idx;
int sz[N];
bool vis[N];
int p[N];

void add(int a, int b, int c) {
  e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}

// 求解u子树的节点个数
int get_sz(int u, int from) {
  if (vis[u]) return 0;
  sz[u] = 1;
  for (int i = h[u]; ~i; i = ne[i]) {
    int v = e[i];
    if (v != from) sz[u] += get_sz(v, u);
  }
  return sz[u];
}

// 求解u子树的重心，返回重心是否找到，将重心存入wc中
bool get_wc(int u, int from, int tot, int &wc) {
  int ms = 0;
  for (int i = h[u]; ~i; i = ne[i]) {
    int v = e[i];
    if (v == from || vis[v]) continue;
    if (get_wc(v, u, tot, wc)) return true;
    ms = max(ms, sz[v]);
  }
  ms = max(ms, tot - sz[u]);
  if (ms <= tot / 2) {
    wc = u;
    return true;
  }
  return false;
}

// 将u子树中所有点与重心的距离存入p数组中，同时返回u子树节点个数
int get_dist(int u, int from, int dist, int &pt) {
  if (vis[u]) return 0;
  int cnt = 1;
  p[pt++] = dist;
  for (int i = h[u]; ~i; i = ne[i]) {
    int v = e[i];
    if (v != from) cnt += get_dist(v, u, dist + w[i], pt);
  }
  return cnt;
}

// 求解p[l : r]中和小于等于m的数对个数
int calc(int l, int r) {
  sort(p + l, p + r + 1);
  int res = 0;
  for (int i = l, j = r; i < j;)
    if (p[i] + p[j] <= m) res += j - i, i++;
    else j--;

  return res;
}

int dfs(int u) {
  // 计算过的点略过
  if (vis[u]) return 0;
  // 求一下重心
  get_wc(u, -1, get_sz(u, -1), u);
  vis[u] = true;

  int res = 0, pt = 0;
  for (int i = h[u]; ~i; i = ne[i]) {
    int v = e[i];
    int cnt = get_dist(v, -1, w[i], pt);
    if (!cnt) continue;
    // 先删掉不合法解
    res -= calc(pt - cnt, pt - 1);
    // 加上从重心出发的解
    int l = pt - cnt, r = pt - 1;
    while (l < r) {
      int mid = l + (r - l + 1 >> 1);
      if (p[mid] <= m) l = mid;
      else r = mid - 1;
    }
    if (p[l] <= m) res += l - (pt - cnt) + 1;
  }
  // 加上两个端点在子树里的解
  res += calc(0, pt - 1);
  
  // 递归求解子树
  for (int i = h[u]; ~i; i = ne[i]) res += dfs(e[i]);
  return res;
}

int main() {
  while (scanf("%d%d", &n, &m), n || m) {
    memset(h, -1, sizeof h);
    memset(vis, 0, sizeof vis);
    idx = 0;
    for (int i = 1; i <= n - 1; i++) {
      int a, b, c;
      scanf("%d%d%d", &a, &b, &c);
      a++, b++;
      add(a, b, c), add(b, a, c);
    }

    printf("%d\n", dfs(1));
  }
}