洛谷P4374 [USACO18OPEN]Disruption P 题解

题意：

Farmer John自豪于他所经营的交通发达的的农场。这个农场是由 $N$ 块牧场（$2 \leq N \leq 50,000$）组成的，$N-1$ 条双向道路将它们连接起来，每一条道路的都为一单位长度。Farmer John注意到，从任何一块牧场到另一块牧场，都能通过一组合适的道路到达。

尽管FJ的农场现在是连通的，他担心如果有一条道路被阻断会发生什么，因为这事实上会将他的农场分为两个不相交的牧场集合，奶牛们只能够在每一个集合内移动但不能在集合间移动。于是FJ又建造了 $M$ 条额外的双向道路（$1 \leq M \leq 50,000$），每一条的长度都是一个至多为 $10^9$ 的正整数。奶牛们仍然可以使用原有的道路进行移动，除非其中的某些被阻断了。

如果某条原有的道路被阻断了，农场就会被分为两块不相交的区域，那么FJ就会从他的额外修建的道路中选择一条能够重建这两块区域的连通性的，取代原来那条，从而奶牛们又可以从任何一块牧场去往另一块牧场。

对于农场上每一条原有的道路，帮助FJ选出最短的替代用的道路。

输入格式：

输入的第一行包含 $N$ 和 $M$ 。接下来的 $N-1$ 行，每行用整数 $p$ 和 $q$ 描述了一条原有的道路，其中 $p \neq q$ 是这条道路连接的两块牧场（在 $1 \cdots N$ 范围内）。剩下的 $M$ 行，每行用三个整数 $p$、$q$ 和 $r$ 描述了一条额外的道路，其中 $r$ 是这条道路的长度。任何两块牧场之间至多只有一条道路。

输出格式：

对原有的 $N-1$ 条道路的每一条，按照它们在输入中出现的顺序，输出如果这条道路被阻断的话，能够重新连接农场的最短的替代用道路的长度。如果不存在合适的替代用的道路，输出 $-1$。

这个题意不看完整有点难懂，反正那 $n-1$ 条边是不算在花费内的，要搞清楚。

考虑原树的一条路径 $u \leadsto v$ ，当新边 $(u,v)$ 添加后，任意 $x \in (u \leadsto v)$ 都可以尝试更新它与父亲连边的答案

因为 $u \leadsto v$ 的任意一条边在删去后仍能通过 $(u,v)$ 连通，额外花费不会超过 $w(u,v)$ 。

问题就变成了一个树上路径取 $\min$ ，考虑树剖，每个点维护它和父亲连边的答案。

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

代码：（注意维护边的树剖要写 id[x] + 1）

#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)(5e4 + 15))
#define ls(at) ((at) << 1)
#define rs(at) ((at) << 1 | 1)

int n,m,pos=1,head[N];
int dep[N],fa[N],sz[N],son[N],top[N],id[N],val[N * 4];
struct Edge { int u,v,next; } e[N * 2];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
void dfs(int u,int f,int d)
{
    dep[u] = d; fa[u] = f; sz[u] = 1;
    int mx = -1;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v; if(v == f) continue; dfs(v,u,d+1);
        sz[u] += sz[v]; if(sz[v] > mx) { son[u] = v, mx = sz[v]; }
    }
}
void dfs(int u,int ftop)
{
    static int tim = 0; top[u] = ftop; id[u] = ++tim;
    if(son[u]) dfs(son[u], ftop);
    for(int i = head[u]; i; i = e[i].next)
    { int v = e[i].v; if(v != fa[u] && v != son[u]) dfs(v,v); }
}
void push_down(int at) { down(val[ls(at)], val[at]); down(val[rs(at)], val[at]); }
void update(int at, int l, int r, int nl, int nr, int k)
{
    if(nl <= l && r <= nr) { return down(val[at], k), void(0); }
    push_down(at); int mid = (l + r) >> 1;
    if(nl <= mid) update(ls(at), l, mid, nl, nr, k);
    if(nr > mid) update(rs(at), mid+1, r, nl, nr, k);
}
void upRange(int x,int y,int v)
{
    while(top[x] != top[y])
    {
        if(dep[top[x]] < dep[top[y]]) swap(x,y);
        update(1,1,n, id[top[x]], id[x], v); x = fa[top[x]];
    }
    if(dep[x] > dep[y]) swap(x,y);
    if(id[x] < id[y]) update(1,1,n, id[x] + 1, id[y], v);
}
int query(int at, int l, int r, int x)
{
    if(l == r) return val[at]; push_down(at); int mid = (l + r) >> 1;
    return (x <= mid) ? query(ls(at), l, mid, x) : query(rs(at), mid + 1, r, x);
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    memset(val, 0x3f, sizeof(val));
    cin >> n >> m;
    for(int i = 1, u, v; i < n; i++)
    {
        cin >> u >> v;
        addEdge(u,v); addEdge(v,u);
    }
    dfs(1,0,1); dfs(1,1);
    for(int i = 1,u,v,w; i <= m; i++) { cin >> u >> v >> w; upRange(u,v,w); }
    for(int i = 1,u,v,res; i < n; i++)
    {
        u = e[i << 1].u, v = e[i << 1].v;
        res = query(1,1,n, id[dep[u] > dep[v] ? u : v]);
        cout << (res == INF ? -1 : res) << '\n';
    }
    return 0;
}