题面

题目描述

公元 $2044$ 年，人类进入了宇宙纪元。

L 国有 $n$ 个星球，还有 $n-1$ 条双向航道，每条航道建立在两个星球之间，这 $n-1$ 条航道连通了 L 国的所有星球。

小 P 掌管一家物流公司，该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 $u_i$ 号星球沿最快的宇航路径飞行到 $v_i$ 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 $j$ ，任意飞船驶过它所花费的时间为 $t_j$ ，并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新， L 国国王同意小 P 的物流公司参与 L 国的航道建设，即允许小 P 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 $m$ 个运输计划。在虫洞建设完成后，这 $m$ 个运输计划会同时开始，所有飞船一起出发。当这 $m$ 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。

如果小 P 可以自由选择将哪一条航道改造成虫洞，试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少？

输入格式

第一行包括两个正整数 $n, m$ ，表示 L 国中星球的数量及小 P 公司预接的运输计划的数量，星球从 $1$ 到 $n$ 编号。

接下来 $n-1$ 行描述航道的建设情况，其中第 $i$ 行包含三个整数 $a_i, b_i$ 和 $t_i$ ，表示第 $i$ 条双向航道修建在 $a_i$ 与 $b_i$ 两个星球之间，任意飞船驶过它所花费的时间为 $t_i$ 。

数据保证

接下来 $m$ 行描述运输计划的情况，其中第 $j$ 行包含两个正整数 $u_j$ 和 $v_j$ ，表示第 $j$ 个运输计划是从 $u_j$ 号星球飞往 $v_j$ 号星球。

输出格式

一个整数，表示小 P 的物流公司完成阶段性工作所需要的最短时间。

样例 #1

样例输入 #1

样例输出 #1

提示

所有测试数据的范围和特点如下表所示

请注意常数因子带来的程序效率上的影响。

对于 $100\%$ 的数据，保证： $1 \leq a_i,b_i \leq n$ ， $0 \leq t_i \leq 1000$ ， $1 \leq u_i,v_i \leq n$ 。

思路

给你 $m$ 条路径，求令一条边边权为零的情况下，所有路径最大值的最小值。

首先想想假如不删边，那么求一下路径和取一个 $\text{max}$ 即可。

假如要删边，也可以想想暴力删这 $n - 1$ 条边，然后求每种情况的最大值然后取一个最小值即可。

复杂度： $O(nmlogn)$

想想怎么优化：

有必要枚举每一条边吗？

首先我们设最大的路径为 T，那么删不在 T 上的边一定不会影响答案，所以要删在 T 上的边，而 T 这条路径可以通过 lca 计算路径长度（ $dist = dist_{u}+dist_{v}-2\times dist_{lca(u,v)}$ ）得到。

那么得到之后我们想想删边后如何确定最大值的最小值。

首先 T 肯定会减少当前边的长度，那么不经过这条边的其它路径呢？

它们可能比变小之后的 T 要大。

这个可以预处理一下 不经过第 i 条边的路径最大值，记为 $tmax$ 。每次添加一条路径时，这条路径的长度可以更新不在这条路径的其它边的 $tmax$ ，那么怎么找边的补集呢？

首先可以把边权转化为深度较深的那个点的点权，然后补集问题显然区间里比较好做，所以可以树链剖分一下，然后记录下路径的每一段区间，然后排一下序，它们之间空出来的就是这条路径的补集。

用线段树维护，单点查询 $tmax$ 的时候也很方便。

注意特判 T 为一个点的情况以及第一个和最后一个区间左右没有多余区间的情况。

复杂度： $O(nmlogn)\to O(mlog^2n)$

代码

#include <bits/stdc++.h>
using namespace std;
#define ls(x) tr[x << 1]
#define rs(x) tr[x << 1 | 1]
const int N = 3e5 + 8;

namespace SegmentTree {
    struct Node
    {
        int l, r;
        int tmax;
        int tag;
    }tr[N << 2];
    void pushup(int u)
    {
        tr[u].tmax = max(ls(u).tmax, rs(u).tmax);
    }
    void pushdown(int u)
    {
        Node &root = tr[u];
        if(root.tag)
        {
            ls(u).tmax = max(ls(u).tmax, root.tag);
            rs(u).tmax = max(rs(u).tmax, root.tag);
            ls(u).tag = max(ls(u).tag, root.tag);
            rs(u).tag = max(rs(u).tag, root.tag);
            root.tag = 0;
        }
    }
    void build(int u, int l, int r)
    {
        tr[u].l = l, tr[u].r = r, tr[u].tag = 0;
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
    }
    void update(int u, int l, int r, int k)
    {
        if(l <= tr[u].l && tr[u].r <= r)
        {
            tr[u].tmax = max(tr[u].tmax, k);
            tr[u].tag = max(tr[u].tag, k);
            return;
        }
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(l <= mid) update(u << 1, l, r, k); //
        if(r > mid) update(u << 1 | 1, l, r, k);
        pushup(u);
    }
    int query(int u, int x)
    {
        if(tr[u].l == tr[u].r) return tr[u].tmax;
        pushdown(u);
        int mid = (tr[u].l + tr[u].r) >> 1;
        if(x <= mid) return query(u << 1, x);
        else return query(u << 1 | 1, x);
    }
}
using namespace SegmentTree;

int n, m;
int A, B, C;
struct Edge
{
    int nxt, to, val;
}e[N << 1];
int fir[N], dep[N], sz[N], id[N], nw[N], w[N], top[N], fa[N], son[N], st[N][25], d[N];
int idx, cnt, root;
void add(int u, int v, int w)
{
    e[++cnt].to = v;
    e[cnt].nxt = fir[u];
    e[cnt].val = w;
    fir[u] = cnt;
}
void dfs1(int u, int fath, int depth)
{
    fa[u] = fath, dep[u] = depth, sz[u] = 1;
    for(int i = fir[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == fath) continue;
        w[v] = e[i].val;
        d[v] = d[u] + e[i].val;
        st[v][0] = u;
        for(int j = 1; j <= 23; j++)
            st[v][j] = st[st[v][j - 1]][j - 1];
        dfs1(v, u, depth + 1);
        sz[u] += sz[v];
        if(sz[son[u]] < sz[v]) son[u] = v;
    }
}
void dfs2(int u, int t)
{
    id[u] = ++idx;
    top[u] = t;
    nw[idx] = w[u];
    if(!son[u]) return;
    dfs2(son[u], t);
    for(int i = fir[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if(v == fa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}
int lca(int x, int y)
{
    if(dep[x] < dep[y]) swap(x, y);
    for(int i = 23; i >= 0; i--)
        if(dep[st[x][i]] >= dep[y])
            x = st[x][i];
    if(x == y) return x;
    for(int i = 23; i >= 0; i--)
        if(st[x][i] != st[y][i])
            x = st[x][i], y = st[y][i];
    return st[x][0];
}
int dist(int u, int v)
{
    int lfa = lca(u, v);
    return d[u] + d[v] - 2 * d[lfa];
}
int x[N], y[N], op[N];
bool cmp(int u, int v)
{
    return x[u] < x[v];
}
void update(int u, int v, int k)
{
    int tot = 0;
    while(top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]]) swap(u, v);
        x[++tot] = id[top[u]];
        y[tot] = id[u];
        u = fa[top[u]];
    }
    if(dep[u] < dep[v]) swap(u, v);
    x[++tot] = id[v] + 1, y[tot] = id[u];
    for(int i = 1; i <= tot; i++) op[i] = i;
    sort(op + 1, op + tot + 1, cmp);
    if(x[op[1]] > 1) update(1, 1, x[op[1]] - 1, k);
    if(y[op[tot]] < n) update(1, y[op[tot]] + 1, n, k);
    for(int i = 1; i < tot; i++) update(1, y[op[i]] + 1, x[op[i + 1]] - 1, k);
}
int query(int u, int v)
{
    int res = 0x3f3f3f3f;
    if(u == v) return 0;
    if(dep[u] < dep[v]) swap(u, v);
    int lfa = lca(u, v);
    while(u != v)
    {
        if(dep[u] < dep[v]) swap(u, v);
        if(u != lfa) res = min(res, max(C - w[u], SegmentTree::query(1, id[u]))), u = fa[u];
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i < n; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        if(!root) root = u;
        add(u, v, w);
        add(v, u, w);
    }
    dfs1(root, -1, 1);
    dfs2(root, root);
    build(1, 1, n);
    for(int i = 1; i <= m; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        int sum = dist(u, v);
        update(u, v, sum);
        if(sum > C)
        {
            A = u;
            B = v;
            C = sum;
        }
    }
    printf("%d\n", ::query(A, B));
    return 0;
}

2023-10-12 11:59:37 # OI # Problem #树链剖分 #LCA