TIOJ 1910：喵喵的旅程－續

TIOJ 1910：喵喵的旅程－續

題目大意：給你一張 $N$ 個點 $M$ 條邊的無向連通圖，邊有權重。有 $Q$ 筆操作，每次操作有兩種情況，第一種情況是給你 $a, b, k$，你要將 $a$ 走到 $b$ 所有可能經過的邊的邊權加上 $k$，一條路徑是合法的若且唯若沒有走到重複的邊，第二種情況是給你 $a, b$，請你輸出所有可能路徑上邊最大值的最小值，也就是 $\min_{path}(\text{biggest value on }path)$。

解法：這題實作好複雜，我寫了好幾天...。

首先來看沒有加值操作要怎麼做，可以用跟這題一樣的做法，建一棵最小生成樹，在上面 $\text{LCA}$ 找最大值，如果不會的可以先來寫這題。

再來是可以經過所有邊的情況，可以發現他是一個 $\text{BCC}$(邊)，那加值的時候所有邊都會被加到，因為都有可能走到，那只要維護加上的值，詢問時用 $\text{MST}$ 加上維護的值就好了。如果有很多 $\text{BCC}$，那只要維護每個 $\text{BCC}$ 各自加上的值就好了。

然後是一棵樹的情況，在路徑上加值可以用輕重鏈剖分，取最大值時用線段樹。

最後是所有東西合併起來的情況，這也是實作複雜的地方：我們先把所有點縮成許多 $\text{BCC}$，$\text{BCC}$ 間以橋連接，最後會形成一棵樹。樹鏈剖分時除了要考慮橋，還要多考慮父節點連出的橋的下端點到連向重子節點的橋的上端點的距離，然後對整個 $\text{BCC}$ 加值也是用到樹鏈剖分，不過可以差分用 $\text{BIT}$ 就好了。

最後在樹鏈剖分時要考慮三種 $\text{case}$：第一種是兩個點在同一個 $\text{BCC}$，第二種是兩個 $\text{BCC}$ 所在的鏈相同，第三種是所在的鏈不同，最後就可以 $\text{AC}$ 了 :TLEThinking:。

$\text{Code：}$

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define TIOJQQ ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

#define lpos pos*2
#define rpos pos*2+1

const int INF = 1e9;
const int SIZE = 1e5 + 5;
const int H = __lg (SIZE) + 1;

// for all
int T, N, M, Q;
vector<pair<int, int>> adj[SIZE];

// for BCC
int dfcnt, bccnt;
vector<int> st;
int dfn[SIZE], low[SIZE], bcc[SIZE], bcp[SIZE];

// for MST
int dto[SIZE], dh[SIZE];
vector<pair<int, int>> mst_adj[SIZE];
vector<tuple<int, int, int>> e[SIZE];
int h[SIZE], to[SIZE][H + 1], dp[SIZE][H + 1];

// for BIT
int bitid, bid[SIZE], bit[SIZE];

// for HLD
vector<tuple<int, int, int, int>> bcc_adj[SIZE];
int dfsid, val[2 * SIZE], mx[8 * SIZE], lazy[8 * SIZE];
int weight[SIZE], pa[SIZE], son[SIZE], sw[SIZE], dep[SIZE], tp[SIZE], id[SIZE], up[SIZE], dn[SIZE], path[SIZE];

// tarjan
void tarjan (int pos, int fa) {
    dfn[pos] = low[pos] = ++dfcnt;
    st.pb (pos);
    for (auto [np, w] : adj[pos]) if (np != fa) {
        if (!dfn[np]) {
            tarjan (np, pos);
            low[pos] = min (low[pos], low[np]);
            if (dfn[pos] < low[np]) {
                bccnt++;
                bcp[bccnt] = np;
                while (1) {
                    int x = st.back();
                    bcc[x] = bccnt;
                    st.pop_back();
                    if (x == np) break;
                }
            }
        } else {
            low[pos] = min (low[pos], dfn[np]);
        }
    }
    if (pos == fa) {
        bccnt++;
        bcp[bccnt] = pos;
        while (st.size()) {
            int x = st.back();
            bcc[x] = bccnt;
            st.pop_back();
        }
    }
}

// dsu
int dsu (int x) {
    return x == dto[x] ? x : (dto[x] = dsu (dto[x]));
}

bool Merge (int a, int b) {
    a = dsu (a), b = dsu (b);
    if (a == b) return 0;
    if (dh[a] < dh[b]) swap (a, b);
    dto[b] = a;
    dh[a] += dh[a] == dh[b];
    return 1;
}

//bit
void update (int l, int r, int x) {
    for (int pos = l; pos <= bitid; pos += pos & -pos) bit[pos] += x;
    for (int pos = r + 1; pos <= bitid; pos += pos & -pos) bit[pos] -= x;
}

int query (int pos) {
    int re = 0;
    for (; pos; pos -= pos & -pos) re += bit[pos];
    return re;
}

// lca
pair<int, int> jump (int pos, int k) {
    int cnt = 0, re = -INF;
    while (k) {
        if (k & 1) {
            re = max (re, dp[pos][cnt]);
            pos = to[pos][cnt];
        }
        cnt++;
        k >>= 1;
    }
    return {pos, re};
}

int cal (int a, int b) {
    int re;
    if (h[a] < h[b]) swap (a, b);
    tie (a, re) = jump (a, h[a] - h[b]);
    if (a == b) return re + query (bid[bcc[a]]);
    for (int i = H; i >= 0; i--) {
        if (to[a][i] != to[b][i]) {
            re = max ({re, dp[a][i], dp[b][i]});
            a = to[a][i];
            b = to[b][i];
        }
    }
    return max ({re, dp[a][0], dp[b][0]}) + query (bid[bcc[a]]);
}

// segtree
void build (int pos, int l, int r) {
    if (l == r) {
        mx[pos] = val[l];
        return;
    }
    int mid = (l + r) / 2;
    build (lpos, l, mid);
    build (rpos, mid + 1, r);
    mx[pos] = max (mx[lpos], mx[rpos]);
}

void Push (int pos, int l, int r) {
    mx[pos] += lazy[pos];
    if (l < r) {
        lazy[lpos] += lazy[pos];
        lazy[rpos] += lazy[pos];
    }
    lazy[pos] = 0;
}

void Pull (int pos, int l, int r) {
    int mid = (l + r) / 2;
    Push (lpos, l, mid);
    Push (rpos, mid + 1, r);
    mx[pos] = max (mx[lpos], mx[rpos]);
}

void update (int pos, int l, int r, int L, int R, int x) {
    if (l == L && r == R) {
        lazy[pos] += x;
        return;
    }
    Push (pos, L, R);
    int mid = (L + R) / 2;
    if (r <= mid) update (lpos, l, r, L, mid, x);
    else if (l > mid) update (rpos, l, r, mid + 1, R, x);
    else {
        update (lpos, l, mid, L, mid, x);
        update (rpos, mid + 1, r, mid + 1, R, x);
    }
    Pull (pos, L, R);
}

int query (int pos, int l, int r, int L, int R) {
    Push (pos, L, R);
    if (l == L && r == R) return mx[pos];
    int mid = (L + R) / 2;
    if (r <= mid) return query (lpos, l, r, L, mid);
    if (l > mid) return query (rpos, l, r, mid + 1, R);
    return max (query (lpos, l, mid, L, mid), query (rpos, mid + 1, r, mid + 1, R));
}

//build HLD
void dfs1 (int pos) {
    weight[pos] = 1;
    for (auto [np, ii, jj, w] : bcc_adj[pos]) if (np != pa[pos]) {
        pa[np] = pos;
        dep[np] = dep[pos] + 1;
        up[np] = ii;
        dn[np] = jj;
        dfs1 (np);
        weight[pos] += weight[np];
        if (weight[np] > weight[son[pos]]) son[pos] = np, sw[pos] = w;
    }
}

void dfs2 (int pos, int t) {
    tp[pos] = t;
    bid[pos] = ++bitid;
    if (!son[pos]) return;
    if (pos != 1) {
        val[++dfsid] = cal (dn[pos], up[son[pos]]);
        path[pos] = dfsid;
    }
    val[++dfsid] = sw[pos];
    id[son[pos]] = dfsid;
    dfs2 (son[pos], t);
    for (auto [np, ii, jj, w] : bcc_adj[pos]) if (np != pa[pos] && np != son[pos]) {
        val[++dfsid] = w;
        id[np] = dfsid;
        dfs2 (np, np);
    }
}

// operation
void Add (int a, int b, int k) {
    int A = bcc[a], B = bcc[b], l, r;
    while (1) {
        if (A == B) {
            update (bid[A], bid[A], k);
            l = r = path[A];
            if (l) update (1, l, r, 1, dfsid, k);
            return;
        }
        if (tp[A] == tp[B]) {
            if (dep[A] > dep[B]) swap (A, B), swap (a, b);
            update (bid[A], bid[B], k);
            l = path[A];
            r = path[B];
            if (l == 0) l = id[son[A]];
            if (r == 0) r = id[B];
            update (1, l, r, 1, dfsid, k);
            return;
        }
        if (dep[tp[A]] < dep[tp[B]]) swap (A, B), swap (a, b);
        update (bid[tp[A]], bid[A], k);
        l = id[tp[A]], r = path[A];
        if (r == 0) r = id[A];
        update (1, l, r, 1, dfsid, k);
        a = up[tp[A]];
        A = pa[tp[A]];
    }
}

int Query (int a, int b) {
    int A = bcc[a], B = bcc[b], l, r, re = -INF;
    while (1) {
        if (A == B) {
            if (a != b) re = max (re, cal (a, b));
            return re;
        }
        if (tp[A] == tp[B]) {
            if (dep[A] > dep[B]) swap (A, B), swap (a, b);
            re = max (re, cal (a, up[son[A]]));
            re = max (re, cal (b, dn[B]));
            l = id[son[A]];
            r = id[B];
            re = max (re, query (1, l, r, 1, dfsid));
            return re;
        }
        if (dep[tp[A]] < dep[tp[B]]) swap (A, B), swap (a, b);
        re = max (re, cal (a, dn[A]));
        l = id[tp[A]], r = id[A];
        re = max (re, query (1, l, r, 1, dfsid));
        a = up[tp[A]];
        A = pa[tp[A]];
    }
}

void solve() {
    cin >> T >> N >> M >> Q;

    // find BCC
    while (M--) {
        int a, b, w;
        cin >> a >> b >> w;
        a++, b++;
        adj[a].pb (b, w);
        adj[b].pb (a, w);
    }
    tarjan (1, 1);

    // add edge of BCC tree and MST
    FOR (i, 1, N) {
        dto[i] = i;
        for (auto [j, w] : adj[i]) {
            if (bcc[i] == bcc[j]) e[bcc[i]].pb (w, i, j);
            else bcc_adj[bcc[i]].pb (bcc[j], i, j, w);
        }
    }

    //build MST
    FOR (i, 1, bccnt) {
        sort (e[i].begin(), e[i].end());
        for (auto [w, a, b] : e[i]) {
            if (Merge (a, b)) {
                mst_adj[a].pb (b, w);
                mst_adj[b].pb (a, w);
            }
        }
        queue<int> q;
        h[bcp[i]] = 1;
        q.push (bcp[i]);
        while (q.size()) {
            int pos = q.front();
            q.pop();
            for (auto [np, w] : mst_adj[pos]) if (!h[np]) {
                h[np] = h[pos] + 1;
                to[np][0] = pos;
                dp[np][0] = w;
                q.push (np);
            }
        }
    }
    FOR (j, 1, H) FOR (i, 1, N) {
        to[i][j] = to[to[i][j - 1]][j - 1];
        dp[i][j] = max (dp[i][j - 1], dp[to[i][j - 1]][j - 1]);
    }

    // build HLD
    dep[1] = 1;
    dfs1 (1);
    dfs2 (1, 1);

    // query
    if (dfsid) build (1, 1, dfsid);
    while (Q--) {
        int ty, a, b, k;
        cin >> ty >> a >> b;
        a++, b++;
        if (ty == 0) cin >> k, Add (a, b, k);
        else cout << Query (a, b) << '\n';
    }
}

int main() {
    TIOJQQ;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！