Author: lllyouo
Date: 20250316
tag: 树的直径
link: https://www.acwing.com/problem/content/353/

问题描述

link

分析

略

参考代码

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

const int N = 5e5 + 10, M = 2 * N;
int h[N], e[M], w[M], ne[M], idx;
int d[N], a[N], prv[N], vis[N], f[N], sum[N], b[N];
int n, s, t;

void add(int a, int b, int c) {
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx++;
}

int bfs(int s) {
    memset(d, -1, sizeof d);
    queue<int> q;
    q.push(s);
    d[s] = 0;
    
    while (q.size()) {
        int u = q.front(); q.pop();
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (d[v] == -1) {
                d[v] = d[u] + w[i];
                prv[v] = i;
                q.push(v);
            }
        }
    }
    
    int p = s;
    for (int i = 1; i <= n; i++) {
        if (d[i] > d[p]) p = i;
    }
    
    return p;
}

void dfs(int x) {
    vis[x] = true;
    for (int i = h[x]; i != -1; i = ne[i]) {
        int y = e[i];
        if (vis[y]) continue;
        dfs(y);
        f[x] = max(f[x], f[y] + w[i]);
    }
}

int main() {
    memset(h, -1, sizeof h);
    cin >> n >> s;
    for (int i = 1; i < n; i++) {
        int a, b, c; cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    
    int p = bfs(1);
    int q = bfs(p);
    
    while (q != p) {
        a[++t] = q;
        b[t + 1] = w[prv[q]];
        q = e[prv[q] ^ 1];
    }
    a[++t] = p;
    
    for (int i = 1; i <= t; i++) vis[a[i]] = true;
    
    int maxf = 0;
    for (int i = 1; i <= t; i++) {
        dfs(a[i]);
        maxf = max(maxf, f[a[i]]);
        sum[i] = sum[i - 1] + b[i];
    }
    
    int ans = 1 << 30;
    for (int i = 1, j = 1; i <= t; i++) {
        while (j < t && sum[j + 1] - sum[i] <= s) j++;
        ans = min(ans, max(maxf, max(sum[i], sum[t] - sum[j])));
    }
    cout << ans << endl;
    
    return 0;
}