「Bzoj 1999」「Noip2007」树网的核加强版 (树的直径+尺取法)

BZOJ 1999
题意：在直径上找到一个区间使得这个区间上所有点的偏心距最小。

容易想到用单调队列CF 1004E的做法。

这里其实偏心距求个最大值即可，就不用单调队列了，直接尺取。

突然发现这题和CF 1004E是一题。。

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 500000 + 5;

    struct edge {
        int v, w, nxt;
    } ed[MAXN * 2];

    int n, s, en, hd[MAXN], whw1, whw2, vis[MAXN], cnt;
    LL dis[MAXN];

    void ins(int x, int y, int w) {ed[++en] = (edge){y, w, hd[x]}, hd[x] = en;}

    void dfs1(int u, int fa) {
        for (int i = hd[u]; i > 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v != fa) {
                dis[e.v] = dis[u] + e.w;
                dfs1(e.v, u);
            }
        }
    }
    int dfs2(int u, int fa) {
        if (u == whw2) return vis[u] = 1, true;
        int fl = 0;
        for (int i = hd[u]; i > 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v != fa) {
                fl |= dfs2(e.v, u);
                if (fl) vis[u] = 1;
            }
        }
        return fl;
    }
    LL gg = 0ll;
    void dfs4(int u, LL D, int fa) {
        gg = max(gg, D);
        for (int i = hd[u]; i > 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v != fa && !vis[e.v]) {
                dfs4(e.v, D + e.w, u);
            }
        }
    }
    void dfs3(int u, LL D, int fa) {
        dis[++cnt] = D;
        for (int i = hd[u]; i > 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v != fa && vis[e.v]) {
                dfs4(e.v, 0, 0);
                dfs3(e.v, D + e.w, u);
            }
        }
    }

    void clean() {
        en = 0, ms(hd, -1), ms(vis, 0);
    }
    int solve() {
        clean();
        scanf("%d%d", &n, &s);
        for (int x, y, w, i = 1; i < n; ++i) {
            scanf("%d%d%d", &x, &y, &w);
            ins(x, y, w), ins(y, x, w);
        }
        ms(dis, 0), dfs1(1, 0);
        whw1 = 0;
        for (int i = 1; i <= n; ++i) if (dis[whw1] < dis[i]) whw1 = i;
        ms(dis, 0), dfs1(whw1, 0);
        whw2 = 0;
        for (int i = 1; i <= n; ++i) if (dis[whw2] < dis[i]) whw2 = i;
        vis[whw1] = 1, dfs2(whw1, 0);
        ms(dis, 0), cnt = 0, dfs3(whw1, 0, 0);
        int l = 1;
        LL ans = 4223372036854775808ll;
        for (int r = 1; r <= cnt; ++r) {
            while (l < r && dis[r] - dis[l] > s) ++l;
            ans = min(ans, max(dis[l], max(dis[cnt] - dis[r], gg)));
        }
        cout << ans;
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}