自动搬运

查看原文

来自洛谷，原作者为

	Joww **

搬运于2025-08-24 22:57:48，当前版本为作者最后更新于2024-09-24 16:37:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

由于题目给定一棵树，因此相连通的三条边要么是链，要么是菊花。

菊花比较简单，做法是——

• 枚举菊花的中心结点 $i$，
• 取出结点 $i$ 的三条边权最大的邻接边，
• 此时这三条边就是以结点 $i$ 为中心且边权和最大的三条边组成的菊花。

对于链，每条链最特殊的边是位于中间的那条，所以做法是——

• 枚举链的中心边 $(i, x)$（边权为 $y$），记为①边；
• 取出 $i$ 的、不与 $x$ 相连的、边权最大的邻接边，记为②边；
• 取出 $x$ 的、不与 $i$ 相连的、边权最大的邻接边，记为③边；
• 【①、②、③】就是以①边为中心边且边权和最大的三条边组成的链。

因此，影响答案的只有每个点边权最大的三条邻接边，预处理后朴素地枚举即可。

为了实现方便，以下代码使用了 sort，但实际上可以使用循环在 $O(n)$ 内找出边权最大的三条边。

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

const int N = (int) 2e5 + 10;
vector<pair<int, int>> g[N];

int main() {
    int n;
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        g[i].push_back({ y, x });
        g[x].push_back({ y, i });
    }
    
    long long ans = 0;
    
    // type1 : flower
    for (int i = 1; i <= n; i++) {
        sort(g[i].begin(), g[i].end(), greater<pair<int, int>>());
        if (g[i].size() >= 3) {
            ans = max(ans, 0ll + g[i][0].first + g[i][1].first + g[i][2].first);
        }
    }

    // type2 : chain
    for (int i = 1; i <= n; i++) {
        if (g[i].size() == 1) continue;
        for (auto [y, x] : g[i]) {
            if (g[x].size() == 1) continue;
            long long sum = y;
            sum += (g[x][0].second != i ? g[x][0] : g[x][1]).first;
            sum += (g[i][0].second != x ? g[i][0] : g[i][1]).first;
            ans = max(ans, sum);
        }
    }
    cout << ans << '\n';

    return 0;
}

Bonus: 如果题目给定的不是树，而是一张图，又该怎么做呢？