[ICPC 2002 Kaohsiung R] 树的重量

GitHub跳转原题关系图返回列表

利用叶子枝长公式 limb(x)=min((d(x,i)+d(x,j)-d(i,j))/2)，递归删去一个叶子并累加其独有边长，最终得到整棵树的总重量。

OJ: luogu

题目 ID: P1268

难度:普及+/提高

标签:树递归推导思维

日期: 2026-06-20 23:55

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

给出一棵带非负整数边权树的叶子两两距离矩阵。

矩阵保证合法，也就是说确实存在某棵树满足这些叶子间距离。

现在不要求恢复整棵树，只要求输出这棵树所有边权之和。

思路

先看一个可以直接验证想法的朴素解：

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 35;
const int INF = 1e9;

int n;
int dis[MAXN][MAXN];

// brute.cpp：小数据验证版。
// 思路和正式解一致，但直接用最朴素的三重枚举去找每次删掉叶子的枝长。
int solve_bruteforce(int size_now) {
    if (size_now == 2) {
        return dis[1][2];
    }

    int x = size_now;
    int limb = INF;

    for (int i = 1; i <= size_now - 1; i++) {
        for (int j = 1; j <= size_now - 1; j++) {
            if (i == j) {
                continue;
            }
            int value = (dis[x][i] + dis[x][j] - dis[i][j]) / 2;
            limb = min(limb, value);
        }
    }

    return solve_bruteforce(size_now - 1) + limb;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        dis[i][i] = 0;
    }

    for (int i = 1; i <= n - 1; i++) {
        for (int j = i + 1; j <= n; j++) {
            cin >> dis[i][j];
            dis[j][i] = dis[i][j];
        }
    }

    cout << solve_bruteforce(n) << '\n';
    return 0;
}

这题最关键的不是构造整棵树，而是发现：

如果当前有一个叶子 xx，它连向树内部的那条边长度记为 limb(x)limb(x)，那么：

limb(x)=min((d(x,i)+d(x,j)−d(i,j))/2)limb(x) = min ((d(x,i) + d(x,j) - d(i,j)) / 2)

这里最小值是在所有 ii、jj 都不是 xx 的叶子对里取。

原因是：

  • 对任意 ii、jj，这个式子都不会小于 xx 的真实枝长
  • 当 ii、jj 分别落在 xx 接入点的两侧时，会恰好取到等号

于是问题就能递归解决：

  1. 求出当前最后一个叶子的枝长
  2. 把它加入答案
  3. 删除这个叶子
  4. 继续处理剩下的叶子

为什么可以直接删？

因为删掉一个叶子以及它独有的末端边，不会影响其他叶子之间的距离，所以剩余部分还是同类问题。

递归到只剩两个叶子时，树就只剩一条边，答案就是它们之间的距离。

代码

cpp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 35;
const int INF = 1e9;

int n;
int dis[MAXN][MAXN];

// 计算当前最后一个叶子 x 连到树上的那条“枝长”。
int get_limb_length(int size_now) {
    int x = size_now;
    int best = INF;
    for (int i = 1; i <= size_now - 1; i++) {
        for (int j = i + 1; j <= size_now - 1; j++) {
            int value = (dis[x][i] + dis[x][j] - dis[i][j]) / 2;
            if (value < best) {
                best = value;
            }
        }
    }
    return best;
}

// 递归删除最后一个叶子，累加它独有的那条边长。
int solve(int size_now) {
    if (size_now == 2) {
        return dis[1][2];
    }
    int limb = get_limb_length(size_now);
    return solve(size_now - 1) + limb;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        dis[i][i] = 0;
    }

    // 输入的是上三角矩阵。
    for (int i = 1; i <= n - 1; i++) {
        for (int j = i + 1; j <= n; j++) {
            cin >> dis[i][j];
            dis[j][i] = dis[i][j];
        }
    }

    cout << solve(n) << '\n';
    return 0;
}

复杂度

每次求一个叶子的枝长要枚举两重叶子对，复杂度是 O(k2)O(k^2)。

总时间复杂度：

O(n3)O(n^3)

空间复杂度：

O(n2)O(n^2)

总结

这题的核心不是“把树建出来”，而是抓住叶子独有边长的三点公式。

一旦想到：

  • 叶子可以一个个删掉
  • 删掉前先用距离矩阵算出它的枝长

总重量就能直接递归算出来。