点分治

还是一道点分治，和前面那道题不同的是求所有距离小于等于k的点对。

如果只是等于k，我们可以把重心的每个子树分开处理，统计之后再合并，这样可以避免答案重复（也就是再同一个子树中出现路径之和为k的点）

但是对于这道题，如果我们还要这样求的话显然是会超时的，意外要枚举所有点的话有点勉强 。。。

考虑一次把重心的子树全部遍历，统计到重心的距离，放进数组中，排序。然后我们可以用指针对撞的方法，用l，r两个指针分别从前后开始扫描。

容易发现，当指针再l的位置时，如果我们记录距离排好序的数组rd[l] + rd[r] <= k, 那么我们可以直接统计答案（r-l），之后l++，如果rd[l] + rd[r] > k,那么我们就让r--。

但是这样并不是正确的答案，因为这样我们再同一个子树中距离小于等于k的点也被算进去了，我们需要再下一次分治处理子树重心之前减去他。

具体方法就是，我们再重心rt的子树u中，去找距离之和为k-2*dis(rt, u)的点对，答案减去它就行了。有个小技巧，我们可以直接把u距离自己的距离设置成dis(rt,u)，这样的话我们还是可以在他的子树中查找距离为k的点对，实际上就是默认给每个点到u的距离都加了dis(rt,u)

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

#define full(a, b) memset(a, b, sizeof a)

using namespace std;

typedef long long ll;

inline int lowbit(int x){ return x & (-x); }

inline int read(){

    int X = 0, w = 0; char ch = 0;

    while(!isdigit(ch)) { w |= ch == '-'; ch = getchar(); }

    while(isdigit(ch)) X = (X << 3) + (X << 1) + (ch ^ 48), ch = getchar();

    return w ? -X : X;

}

inline int gcd(int a, int b){ return a % b ? gcd(b, a % b) : b; }

inline int lcm(int a, int b){ return a / gcd(a, b) * b; }

template<typename T>

inline T max(T x, T y, T z){ return max(max(x, y), z); }

template<typename T>

inline T min(T x, T y, T z){ return min(min(x, y), z); }

template<typename A, typename B, typename C>

inline A fpow(A x, B p, C lyd){

    A ans = 1;

    for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;

    return ans;

}

const int N = 60005;

int n, k, cnt, ans, rt, sum, tot, res, head[N], size[N], dis[N], rd[N];

bool vis[N];

struct Edge { int v, next, w; } edge[N<<2];

void addEdge(int a, int b, int c){

    edge[cnt].v = b, edge[cnt].w = c, edge[cnt].next = head[a], head[a] = cnt ++;

}

void dfs(int s, int fa){

    int mp = 0;

    size[s] = 1;

    for(int i = head[s]; i != -1; i = edge[i].next){

        int u = edge[i].v;

        if(u == fa || vis[u]) continue;

        dfs(u, s);

        size[s] += size[u];

        mp = max(mp, size[u]);

    }

    mp = max(mp, sum - size[s]);

    if(mp < ans) ans = mp, rt = s;

}

void getDis(int s, int fa){

    rd[++tot] = dis[s];

    for(int i = head[s]; i != -1; i = edge[i].next){

        int u = edge[i].v;

        if(u == fa || vis[u]) continue;

        dis[u] = dis[s] + edge[i].w;

        getDis(u, s);

    }

}

int calc(int s, int w){

    dis[s] = w;

    tot = 0, getDis(s, 0);

    sort(rd + 1, rd + tot + 1);

    int l = 1, r = tot, ret = 0;

    while(l <= r) rd[l] + rd[r] <= k ? (ret += r - l, l ++) : (r --);

    return ret;

}

void solve(int s){

    res += calc(s, 0);

    vis[s] = true;

    for(int i = head[s]; i != -1; i = edge[i].next){

        int u = edge[i].v;

        if(vis[u]) continue;

        res -= calc(u, edge[i].w);

        ans = INF, sum = size[u];

        dfs(u, 0), solve(rt);

    }

}

int main(){

    full(head, -1);

    n = read();

    for(int i = 0; i < n - 1; i ++){

        int u = read(), v = read(), c = read();

        addEdge(u, v, c), addEdge(v, u, c);

    }

    k = read();

    ans = INF, sum = n;

    dfs(1, 0), solve(rt);

    printf("%d\n", res);

    return 0;

}