题解：P8602 [蓝桥杯 2013 省 A] 大臣的旅费

chrispang · 2025-08-11 21:07:50 · 题解

题目大意

给出一棵树，设这棵树的直径长度为 x，则答案为：

树的结点数量不超过 10^5。

题目分析

我们可以考虑每一个节点 x，假设树中的直径经过 x 且在 x 子树中。那么树的直径长度应为：x 子树中到达 x 的最长路 + x 子树中到达 x 的次长路。如图，粉色路径与橙色路径可以构成一条直径：

因此，我们可以考虑使用 DP 求出最长路与次长路：

• 状态：定义 f_{i,0/1} 表示在 i 的子树中，达到 i 的最长路或次长路（0 和 1 分别表示最长路与次长路）

• 状态转移方程：

::::success[点我点我] 遍历 i 的每个儿子，设 i 到其儿子的距离为 w。分两种情况：

• 若 f_{son,0}+w \ge f_{i,0}，则 f_{i,1}=f{i,0},f_{i,0}=f_{son,0}+w。

• 若上述条件不满足，且 f_{son,0}+w > f_{i,1}，则 f_{i,1}=f_{son,0}+w。 ::::

• 初始化：每个叶子节点的 f_{i,0/1} 设为 0。

• 答案：\max_{i=1}^n\{f_{i,0}+f_{i,1}\}。

代码实现

#include <bits/stdc++.h>
#define maxn 10010
using namespace std;

struct edge {
    int to, w;
};

int n, ans = -1e9, dis[maxn], f[maxn][2];
vector<edge> linker[maxn];
void add(int x, int y, int w) {
    linker[x].push_back({y, w});
}

void dfs(int x, int fa) {
    // 遍历每个儿子
    for (auto v : linker[x])
        if (v.to != fa) dfs(v.to, x);

    // 跑 DP，计算子树中的最长路和次长路
    for (auto v : linker[x]) {
        int son = v.to, w = v.w;
        if (son == fa) continue;
        if (f[son][0] + w >= f[x][0]) f[x][1] = f[x][0], f[x][0] = f[son][0] + w;
        else if (f[son][0] + w > f[x][1]) f[x][1] = f[son][0] + w;
    }
    ans = max(ans, f[x][0] + f[x][1]);
}

int main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y, w;
        cin >> x >> y >> w;
        add(x, y, w), add(y, x, w);
    }
    dfs(1, 0);
    cout << (ans * 10 + ans * (ans + 1) / 2) << endl;
    return 0;
}