【题解】uoj237 && 298 shortcut

题意:

给定一颗有边权的树 $T$，加入一条长度为 $len$的边，最小化直径。

Sol:

首先可以发现新加的边端点一定在原树的某条直径上，问题变成一个序列上的问题。

记 $pos_i$为 $i$在序列中的坐标，$h_i$为 $i​$下面挂的链长。

首先二分答案，假设新加的边的端点 $(a,b), a < b$以及对于所有的 $i < j$，满足一下两个关系之一

$pos_j – pos_i + h_i + h_j \leq mid \tag 1 \label 1$
$h_i + h_j + | pos_j – pos_b | + |pos_i – pos_a | + len \leq mid \tag 2 \label 2$

记 $y_j = pos_j – h_j, z_j = pos_j + h_j$。

$\eqref 1$式等价于 $z_j + y_i \leq mid$，$\eqref 2$式可以通过拆绝对值，转化成四个关于 $\pm pos_a \pm pos_b\leq limit$的方程，之后双指针扫描边界就行了。

接下来我们只需要求出所有 $i < j$且不满足 $\eqref 1$的 $limit$最大值。

初步的想法是对于 $z_j, y_j​$排序，但是不是很好处理 $i < j​$的限制，(貌似不需要处理？？？

我们可以发现对于给定的 $j​$，对于 $i_1 < i_2 < j​$，如果 $y_1 < y_2​$，$i_1​$对 $limit​$是没有贡献的。

首先他在 $\eqref 1$是会尽早 pass 掉，在 $\eqref 2$式中 $i_1 < i_2 \iff pre_{i_1} < pre_{i_2}$，又 $y_1 < y_2 \rightarrow z_1 < z_2$，而关于 $limit$的式子是形如 $\pm y_j \pm z_j + k \leq limit$的 。

用单调队列维护 $y_i​$就可以了。

#include <bits/stdc++.h>
#include "shortcut.h"
#define rep(i, n) for (rint i = 1; i <= (n); i ++)
#define re0(i, n) for (rint i = 0; i < (int) n; i ++)
#define travel(i, u) for (rint i = head[u]; i; i = e[i].nxt)
#define rint register int
using namespace std;

typedef long long lo;

const lo inf = 1e18;
const int N = 2e6 + 233;
int n, vs;
lo len, pre[N], np[N], h[N];

inline bool check(lo mid) {
    lo A = -inf, B = -inf, C = -inf, D = -inf;
    lo Neg = -inf, Pos = -inf;
    deque <int> q;
    for (int j = 1; j <= n; j++) {
        while (q.size()) {
            int i = q.front();
            if (pre[j] - pre[i] + h[i] + h[j] > mid) {
                Neg = max(Neg, h[i] + pre[i]);
                Pos = max(Pos, h[i] - pre[i]);
                q.pop_front();
            } else break;
        }
        A = max(A, h[j] + pre[j] + Neg);
        C = max(C, h[j] + pre[j] + Pos);
        B = max(B, h[j] - pre[j] + Neg);
        D = max(D, h[j] - pre[j] + Pos);
        while (q.size() && h[q.back()] - pre[q.back()] < h[j] - pre[j]) q.pop_back();
        q.push_back(j);
    }
    A = mid - len - A; B = mid - len - B;
    C = mid - len - C; D = mid - len - D;
    int lx = 1, rx = 1, ly = n, ry = n;
    for (int b = 1; b <= n; b++) {
        while (lx <= n && !(np[lx] >= np[b] - B)) lx++;
        while (rx + 1 <= n && np[rx + 1] <= C + np[b]) rx++;
        while (ly - 1 >= 1 && np[ly - 1] >= -np[b] - A) ly--;
        while (ry >= 1 && !(np[ry] <= -np[b] + D)) ry--;
        if (ly > ry || lx > rx) continue;
        if (!(rx < ly || ry < lx)) return true;
    }
    return false;
}

lo find_shortcut(int _n, vector<int> _l, vector<int> d, int c) {
    n = _n; len = c;
    pre[1] = 0;
    rep (i, n) pre[i + 1] = _l[i - 1] + pre[i];
    memcpy(np, pre, sizeof np);
    sort(np + 1, np + n + 1);
    rep (i, n) h[i] = d[i - 1];
    lo l = *max_element(h + 1, h + n + 1), r = 0, prefix = 0;
    rep (i, n) {
        r = max(r, prefix + pre[i] + h[i]);
        prefix = max(prefix, h[i] - pre[i]);
    }
    while (l < r) {
        lo mid = l + (r - l) / 2;
        check(mid) ? r = mid : l = mid + 1;
    }
    return r;
}