洛谷P3771 [CTSC2017]网络题解

题目链接：P3771 [CTSC2017]网络

题意：

一个一般的网络系统可以被描述成一张无向连通图。图上的每个节点为一个服务器，连接服务器与服务器的数据线则看作图上的一条边，边权为该数据线的长度。两个服务器之间的通讯距离定义为其对应节点之间最短路的长度。

现在，考虑一个当前图结构为树的网络系统。你作为该网络系统的管理员，被要求在这个系统中新加入一条给定长度的数据线。数据线可以连在任意两个服务器上。你的任务是，求出在所有合法的方案中，通讯距离最远的两个服务器之间的最小距离。

输入格式：

输入包含多组数据。对于每组数据，输入的第一行包含二个正整数 \(n,m\) ，其中 \(n\) 表示服务器个数，\(m\) 为新加入数据线的长度。

接下来 \(n − 1\) 行，第 i 行有三个正整数 \(a_i, b_i, l_i\) ，表示有一条长度为 \(l_i\) 的数据线连接服务器 \(a_i, b_i\)。服务器的编号为 \(1 \sim n\) 。

输入的末尾以两个 0 作为结束。

输出格式：

对于每组数据，输出一行一个整数，描述在所有合法的方案中，通讯距离最远的两个服务器之间的最小距离。

数据范围：

\(1 \le n \le 10^5,\sum n \le 5\times 10^5\) 。

保证所有的输入数据均为不超过 \(2^{31} − 1\) 的非负整数，且数据合法。

容易发现，存在一组最优解，使得新加入的边一定连接树的直径上的两点。

我感觉这个结论挺显然的，找不到反例。详细证明的话可以看 OI中转站。

注意到「最大距离最小」，考虑二分这个大小为 \(x\) ，考虑怎么检查。

设 \(L_i\) 表示到直径一端的距离，\(d_i\) 表示 \(i\) 所在子树以 \(i\) 为端点的最长链。

对于所有 \(L_j - L_i + d_i + d_j > x\) ，满足 \(|L_a - L_i| + |L_b - L_j| + d_i + d_j + c \le x\) ，否则 \(x\) 不可行。

套路地拆开绝对值，如下 \[ \begin{aligned} -L_i-L_j+d_i+d_j+c-D &\leq-L_a-L_b \\ L_i-L_j+d_i+d_j+c-D &\leq L_a-L_b \\ -L_i+L_j+d_i+d_j+c-D &\leq-L_a+L_b \\ L_i+L_j+d_i+d_j+c-D &\leq L_a+L_b \end{aligned} \] 然后我们可以找找 \(L_i + d_i\) 和 \(L_i-d_i\) 之类的最值，然后枚举 \(b\) ，用指针维护右边那几坨的最小值

时间复杂度 \(\mathcal{O}(n \log M)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

char is[N];
int n,m,pos=1,rt,rt2,tot,head[N],dis[N],pre[N],q[N],L[N],d[N];
struct Edge { int u,v,w,next; } e[N * 2];
void addEdge(int u,int v,int w) { e[++pos] = {u,v,w,head[u]}; head[u] = pos; }
void clear()
{
    memset(head, 0, sizeof(head)); pos = 1;
    memset(is, 0, sizeof(is));
}
void dfs(int u,int f)
{
    if(dis[rt] < dis[u]) rt = u;
    for(int i = head[u], v; i; i = e[i].next)
        if((v = e[i].v) != f && !is[v]) { pre[v] = i; dis[v] = dis[u] + e[i].w; dfs(v,u); }
}
bool check(int x)
{
    int PN,PP,NN,NP,NX,PX,cur; int st = 1, en = 1;
    PN = PP = NN = NP = PX = NX = -INF;
    for(int i = 1; i <= tot; i++)
    {
        while(st < en && L[i] + d[i] - L[q[st+1]] + d[q[st+1]] > x)
        { up(PX, L[q[st+1]] + d[q[st+1]]); up(NX, d[q[st+1]] - L[q[st+1]]); ++st; }
        cur = d[i] + m - x;
        up(PP, L[i] + PX + cur); up(PN, cur - L[i] + PX);
        up(NN, cur - L[i] + NX); up(NP, cur + L[i] + NX);
        while(st < en && d[q[en]] - L[q[en]] < d[i] - L[i]) --en;
        q[++en] = i;
    }
    int pos1 = 1, pos2 = tot+1, pos3 = 0, pos4 = tot;
    for(int i = 1; i <= tot; i++)
    {
        while(pos1 <= tot && L[pos1] - L[i] < PN) ++pos1;
        while(pos2 && L[pos2 - 1] + L[i] >= PP) --pos2;
        while(pos3 <= tot && -L[pos3 + 1] + L[i] >= NP) ++pos3;
        while(pos4 && -L[pos4] - L[i] < NN) --pos4;
        if(max(pos1, pos2) <= min(pos3, pos4)) return 1;
    }
    return 0;
}
void work()
{
    for(int i = 1,u,v,w; i < n; i++)
    {
        cin >> u >> v >> w;
        addEdge(u,v,w); addEdge(v,u,w);
    }
    rt = 1, dis[rt] = pre[rt] = 0; dfs(rt, 0);
    int mx=0; dis[rt] = pre[rt] = 0; dfs(rt, 0);
    rt2 = rt, tot = 0, mx = dis[rt2];
    for(int u = rt2; u; u = e[pre[u] ^ 1].v) is[u] = 1;
    for(int u = rt2; u; u = e[pre[u] ^ 1].v)
    {
        L[++tot] = mx - dis[u];
        rt = u; dis[u] = 0; dfs(rt, 0);
        d[tot] = dis[rt];
    }
    int l = 0, r = INF;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        check(mid) ? r = mid : (l = mid + 1);
    }
    cout << l << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    while(cin >> n >> m && n && m) { clear(), work(); }
    return 0;
}