题目分析

题目要求计算树中所有满足距离不超过k的顶点对的数量。树是一种连通无向无环图，顶点对(u,v)和(v,u)视为同一对，且u≠v。

解题思路

1. 分治法：利用树的重心分解来高效解决问题。
2. 树的重心：找到一个节点，使得删除该节点后，最大子树的大小最小化。这有助于将问题分解为更小的子问题。
3. 路径统计：对于每个重心，统计经过该重心的路径中长度不超过k的数目，然后递归处理子树。

标程

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 20010;
int N, K, root, num, ans, cnt, mins;
int Head[MAXN], To[MAXN*2], V[MAXN*2], W[MAXN*2];
int siz[MAXN], dis[MAXN], f[MAXN];

void add(int u, int v, int w) {
    To[++num] = Head[u];
    Head[u] = num;
    V[num] = v;
    W[num] = w;
}

int get_size(int x, int fa) {
    siz[x] = 1;
    for (int h = Head[x]; h; h = To[h]) {
        int o = V[h];
        if (o != fa && !f[o]) {
            siz[x] += get_size(o, x);
        }
    }
    return siz[x];
}

void get_dis(int x, int d, int fa) {
    dis[++cnt] = d;
    for (int h = Head[x]; h; h = To[h]) {
        int o = V[h];
        if (o != fa && !f[o]) {
            get_dis(o, d + W[h], x);
        }
    }
}

void dfs_root(int x, int tot, int fa) {
    int maxs = tot - siz[x];
    for (int h = Head[x]; h; h = To[h]) {
        int o = V[h];
        if (o != fa && !f[o]) {
            maxs = max(maxs, siz[o]);
            dfs_root(o, tot, x);
        }
    }
    if (maxs < mins) {
        mins = maxs;
        root = x;
    }
}

int work(int x, int d) {
    cnt = 0;
    get_dis(x, d, 0);
    sort(dis + 1, dis + cnt + 1);
    int res = 0, i = 1, j = cnt;
    while (i < j) {
        while (i < j && dis[i] + dis[j] > K) j--;
        res += j - i;
        i++;
    }
    return res;
}

void dfs(int x) {
    cnt = 0;
    mins = MAXN;
    get_size(x, 0);
    dfs_root(x, siz[x], 0);
    ans += work(root, 0);
    f[root] = 1;
    for (int h = Head[root]; h; h = To[h]) {
        int o = V[h];
        if (!f[o]) {
            ans -= work(o, W[h]);
            dfs(o);
        }
    }
}

int main() {
    while (scanf("%d%d", &N, &K) != EOF && N && K) {
        memset(Head, 0, sizeof(Head));
        memset(f, 0, sizeof(f));
        num = ans = 0;
        for (int i = 1, u, v, w; i < N; i++) {
            scanf("%d%d%d", &u, &v, &w);
            add(u, v, w);
            add(v, u, w);
        }
        dfs(1);
        printf("%d\n", ans);
    }
    return 0;
}

代码解释

1. 输入处理：读取树的边信息，构建邻接表。
2. 重心分解：
   • get_size：计算子树大小。
   • dfs_root：寻找当前子树的重心。
3. 路径统计：
   • get_dis：收集所有节点到当前重心的距离。
   • work：统计经过当前重心的有效路径数。
4. 分治处理：递归处理子树，避免重复计算。
5. 输出结果：对每个测试用例输出有效顶点对数。

样例解释

对于输入样例：

5 4
1 2 3
1 3 1
1 4 2
3 5 1

有效顶点对为： (1,3), (1,4), (1,5), (3,5), (2,1), (3,1), (4,1), (5,3)共8对，因此输出8。