題意：給一個N個節點的帶權樹，求長度小于等于K的路徑條數
思路：選取一個點作為根root，假設f(root)是當前樹的答案，那么答案來源于兩部分：
（1）路徑不經過root，那么就是完全在子樹內，這部分可以遞歸統計
（2）路徑經過root，這部分可以通過容斥原理統計，具體見有關點分治資料。。。
點分治有個特點，當考慮的問題由根這個子樹轉為兒子的子樹時，可以選取任意點作為新的根，只要它在兒子的子樹內，這就使得我們可以通過選取特別的點使得樹深度更小，這個點就是樹的重心（在程序里面是不斷找子樹的重心），樹分治的復雜度是O(NH+TH)的，其中H是樹的深度，T是每層計算答案的復雜度，重心可以將樹的深度變成O(logN)。
另外，整體看樹分治的遍歷節點的過程，發現它與建堆的過程十分相似，也就從側面說明了樹分治的復雜度。。。
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <map>
#include <vector>
using namespace std;
#define X first
#define Y second
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define mset(a, x) memset(a, x, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(b))
#define cas() int T, cas = 0; cin >> T; while (T --)
template<typename T>bool umax(T&a, const T&b){return a<b?(a=b,true):false;}
template<typename T>bool umin(T&a, const T&b){return b<a?(a=b,true):false;}
typedef long long ll;
typedef pair<int, int> pii;#ifndef ONLINE_JUDGE#include "local.h"
#endifconst int N = 1e4 + 7;
const int M = N;
const int inf = 1e9 + 7;namespace Edge {int last[N], to[M << 1], w[M << 1], next[M << 1], cntE;void init() {cntE = 0;memset(last, -1, sizeof(last));}void addEdge(int u, int v, int w) {to[cntE] = v;Edge::w[cntE] = w;next[cntE] = last[u];last[u] = cntE ++;}
}int n, K;namespace Center {int root, siz, son[N];void init() {siz = inf;}void getRoot(int cur, int fa, int total, bool used[]) {son[cur] = 0;int buf = 0;for (int i = Edge::last[cur]; ~i; i = Edge::next[i]) {int to = Edge::to[i];if (to != fa && !used[to]) {getRoot(to, cur, total, used);son[cur] += son[to] + 1;buf = max(buf, son[to] + 1);}}buf = max(buf, total - son[cur] - 1);if (buf < siz || buf == siz && cur < siz) {siz = buf;root = cur;}}
}void getDepth(int cur, int fa, int sum, vector<int> &vt, bool used[]) {vt.pb(sum);for (int i = Edge::last[cur]; ~i; i = Edge::next[i]) {int to = Edge::to[i], w = Edge::w[i];if (to != fa && !used[to]) getDepth(to, cur, sum + w, vt, used);}
}int getAns(vector<int> &vt) {sort(all(vt));int maxp = vt.size() - 1, ans = 0;for (int i = 0; i < maxp; i ++) {while (i < maxp && vt[i] + vt[maxp] > K) maxp --;ans += maxp - i;}return ans;
}bool used[N];int work(int cur) {used[cur] = true;vector<int> total;total.push_back(0);int ans = 0;for (int i = Edge::last[cur]; ~i; i = Edge::next[i]) {int to = Edge::to[i], w = Edge::w[i];if (!used[to]) {vector<int> local;getDepth(to, cur, w, local, used);ans -= getAns(local);for (int j = 0; j < local.size(); j ++) {total.push_back(local[j]);}Center::init();Center::getRoot(to, cur, local.size(), used);ans += work(Center::root);}}return ans += getAns(total);
}int main() {
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);//freopen("out.txt", "w", stdout);
#endif // ONLINE_JUDGEwhile (cin >> n >> K, n || K) {int u, v, w;Edge::init();Center::init();mset(used, 0);for (int i = 1; i < n; i ++) {scanf("%d%d%d", &u, &v, &w);Edge::addEdge(u, v, w);Edge::addEdge(v, u, w);}Center::getRoot(1, 0, n, used);cout << work(Center::root) << endl;}return 0;
}
