Solution

点分治一下就可以了。

#include <bits/stdc++.h>
using namespace std;
const int N = 40100;
int n, k, ans;
int head[N], nex[N<<1], to[N<<1], val[N<<1], ce;
void add(int u, int v, int w) {
    to[++ce] = v; nex[ce] = head[u]; head[u] = ce; val[ce] = w;
    to[++ce] = u; nex[ce] = head[v]; head[v] = ce; val[ce] = w;
}
int size[N], f[N], used[N], dep[N], root, sum;
void getroot(int x, int fa) {
    size[x] = 1; f[x] = 0;
    for(int i=head[x]; i; i=nex[i]) {
        int v = to[i];
        if(used[v] || v == fa) continue;
        getroot(v, x);
        size[x] += size[v];
        f[x] = max(f[x], size[v]);
    }
    f[x] = max(f[x], sum - size[x]);
    if(f[x] < f[root]) root = x;
}
vector<int> vec;
void getdeep(int x, int fa) {
    vec.push_back(dep[x]);
    for(int i=head[x]; i; i=nex[i]) {
        int v = to[i], w = val[i];
        if(used[v] || v == fa) continue;
        dep[v] = dep[x] + w;
        getdeep(v, x);
    }
}
int cal(int x, int w) {
    vec.clear(); dep[x] = w; getdeep(x, 0);
    sort(vec.begin(), vec.end());
    int res = 0;
    for(int i=0, j=vec.size()-1; i<j; i++) {
        while(i < j && vec[i] + vec[j] > k) j--;
        res += j - i;
    }
    return res;
}
void solve(int x) {
    ans += cal(x, 0);
    used[x] = true;
    for(int i=head[x]; i; i=nex[i]) {
        int v = to[i], w = val[i];
        if(used[v]) continue;
        ans -= cal(v, w);
        root = 0; sum = size[v];
        getroot(v, 0);
        solve(root);
    }
}
int main() {
    scanf("%d", &n);
    for(int i=1; i<=n-1; i++) {
        int u, v, w; scanf("%d%d%d", &u, &v, &w);
        add(u, v, w);
    }
    scanf("%d", &k);
    f[0] = sum = n;
    getroot(1, 0);
    solve(root);
    printf("%d\n", ans);
    return 0;
}

Description

给你一棵TREE,以及这棵树上边的距离.问有多少对点它们两者间的距离小于等于K

Input

N(n<=40000) 接下来n-1行边描述管道,按照题目中写的输入 接下来是k

Output

一行,有多少对点之间的距离小于等于k

Sample Input

7
1 6 13
6 3 9
3 5 7
4 1 3
2 4 20
4 7 2 
10

Sample Output

5