树网的和题解

先放一张图在这里插入图片描述

作为一道蓝题，其实快接近紫题了。

--------------------------------------不怎么华丽的分割线--------------------------------------
前置芝士：树的直径
一个点的最远点( $y$ )到这个最远点的最远点( $p$ )一定是一条树的直径。

假若说我们已知 $y$ 是一个端点，那很简单，一定是

所以只用考虑 $y$ 的位置

如果 $y$ 不在直径上，那么根据树的直径的定义，一定有一个直径端点更远！

具体不细讲了，证明有点烦，但脑补却挺容易的
--------------------------------------不怎么华丽的分割线--------------------------------------
遇到这种题，先别慌 ~~，待会儿有的是时间慌呢~~ ，先把条件拿走，然后发现，如果去掉 $s$ ，这不就是树的直径吗？

然后我们感性猜测一下，答案应该是树的直径上的一条链吧？

如果是IOI，那你就直接试一试，OI则最好证明一下

考虑反证法

如果说不是树的直径上的一条链，则必定这条链与树的直径的点有交集（不然到树的直径的两端就太远了）

那么，就考虑是X形还是Y形了（分一下，好想）

其实X差不多是两个Y相加

那么就考虑Y了

在这里插入图片描述

如图，红线是目前的选法，绿线是在直径上的最佳选法

那么，可以发现，虽然绿线到达枝干（我们称直径以外为枝干，直径为主干）的末端更远，但是到达主干末端却更近根据树的直径的定义，一定是从分叉点到达主干末端更远（起码不会更近）

故而红线的选择其实不影响答案——它只不过是把一个较小数变得更小了，我们要的是最大值！

证毕
--------------------------------------不怎么华丽的分割线--------------------------------------

题目到这里就十分简单了。首先，一定要考虑到直径两端的距离，然后是挂在链上的一堆枝干的最大值。考虑枚举链的左端点，采用双指针维护。链上枝干的最大值比较烦，我懒得想更快的单调队列，用了个RMQ维护

结束了……啊不，给个代码


#include <bits/stdc++.h>
const int N = 300000 + 10;
using namespace std;
int n, c, d[N];
vector<pair<int, int>> E[N];
int e1, e2;
int nxt[N], nxtt[N], a[N], k[N], cnt, s, on[N];
int big[N], dg[N];
void dfs(int u, int fa)
{
    for (auto vv : E[u]) {
        int v = vv.first, w = vv.second;
        if (v == fa)
            continue;
        d[v] = d[u] + w;
        if (d[v] > d[c])
            c = v;
        dfs(v, u);
    }
}
void dfss(int u, int fa)
{
    int cc = 0, cw = 0;
    d[u] = 0;
    for (auto vv : E[u]) {
        int v = vv.first, w = vv.second;
        if (v == fa)
            continue;
        dfss(v, u);
        if (d[v] + w > d[u])
            d[u] = d[v] + w, cc = v, cw = w;
    }
    nxt[u] = cc;
    nxtt[u] = cw;
}
void dffs(int u, int fa)
{
    for (auto vv : E[u]) {
        int v = vv.first, w = vv.second;
        if (v == fa || on[v])
            continue;
        d[v] = d[u] + w;
        if (d[v] > d[c])
            c = v;
        dfs(v, u);
    }
}
int mn[27][N], mx[27][N];
void init()
{
    for (int i = 1; i <= cnt; i++)
        mx[0][i] = big[i];
    for (int i = 1; i <= 26; i++)
        for (int j = 1; j + (1 << i) - 1 <= cnt; j++) {
            mn[i][j] = min(mn[i - 1][j], mn[i - 1][j + (1 << (i - 1))]);
            mx[i][j] = max(mx[i - 1][j], mx[i - 1][j + (1 << (i - 1))]);
        }
}
int gt_min(int x, int y)
{
    int t = log2(y - x + 1);
    return min(mn[t][x], mn[t][y - (1 << t) + 1]);
}
int gt_max(int x, int y)
{
    int t = log2(y - x + 1);
    return max(mx[t][x], mx[t][y - (1 << t) + 1]);
}
int main()
{
    cin >> n >> s;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        E[u].push_back({ v, w }), E[v].push_back({ u, w });
    }
    dfs(1, 0);
    d[c] = 0, e1 = c;
    dfs(c, 0);
    e2 = c;
    dfss(e1, 0);
    memset(d, 0, sizeof d);
    for (int i = e1; i != e2; i = nxt[i])
        a[++cnt] = i,
        on[i] = cnt,
        k[cnt + 1] = nxtt[i];
    for (int i = 1; i <= cnt + 1; i++)
        k[i] += k[i - 1];
    a[++cnt] = e2;
    on[e2] = cnt;
    for (int i = 1; i <= cnt; i++)
        dffs(a[i], 0), big[i] = d[c], c = 0;
    init();
    int ans = 0x3f3f3f3f;
    for (int l = 1, r = 1; l <= cnt; l++) {
        while (r <= cnt && k[r] - k[l] <= s)
            r++;
        --r;
        ans = min(ans, max(gt_max(l, r), max(k[cnt] - k[r], k[l])));
    }
    cout << ans;
    return 0;
}