February 06, 2022, 17th

1. Title Link: P2542 [AHOI2005] Route Planning

Ideas: L C T LCT LCT Plus Set Solution, Time Complexity O ( n l o g   n ) O(nlog\ n) O(nlog n). We find that positive edge deletion is not good to maintain connectivity. Based on the principle of positive and difficult, we can process offline and complete the operation in reverse order. Obviously, each point can represent a double connected component, and the query is the length of the chain minus one, that is, the number of bridges. Connect an edge if L C T LCT LCT is not connected yet l i n k link link, if it's connected, there's a ring here, and then we can violently shrink and use the root of the current auxiliary tree (that is, the tree formed by the collection) as the marker node of the collection, and then d f s dfs dfs entire auxiliary tree, change the other points on the chain and find violence to this marker node, and finally disconnect the marker node from the subtree, that is, the marker node represents the whole subtree. Total number of violent modifications will not exceed n l o g   n nlog\ n nlog n times. Also note that a c c e s s access Update when access ing x x x is F i n d ( f [ x ] ) Find(f[x]) Find(f[x]) .

#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define re register
#define endl '\n'

using namespace std;

const int MOD = 998244353;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double Pi = acos(-1.0);
const int N = 3e4 + 5, M = 1e5 + 5;

#define ls(x) (ch[x][0])
#define rs(x) (ch[x][1])

int fa[N], ch[N][2], siz[N];
int f[N], a[M], b[M];
int op[M], ans[M];
bool rev[N], vis[M];
struct node {
    int x, y;
    bool operator < (const node& r) const {
        return x < r.x || (x == r.x && y < r.y);
    }
}e[M];
inline int ident (int x, int y) { return rs(y) == x; }
inline int find(int x) {
    if (x == f[x]) return x;
    return f[x] = find(f[x]);
}
inline bool nroot (int x) {
    return ls(fa[x]) == x || rs(fa[x]) == x;
}
inline void pushup (int x) { 
    siz[x] = siz[ls(x)] + siz[rs(x)] + 1;
}
inline void pushrev (int x) {
    swap (ls(x), rs(x));
    rev[x] ^= 1;
}
inline void pushdown (int x) {
    if (rev[x]) {
        if (ls(x)) pushrev (ls(x));
        if (rs(x)) pushrev (rs(x));
        rev[x] = 0;
    }
}
inline void rotate (int x) {
    int y = fa[x], z = fa[y], k = ident (x, y);
    if (nroot (y)) ch[z][ident (y, z)] = x;
    ch[y][k] = ch[x][k ^ 1], ch[x][k ^ 1] = y;
    if (ch[y][k]) fa[ch[y][k]] = y;
    fa[x] = z, fa[y] = x;
    pushup (y), pushup (x);
}
int st[N], top;
inline void splay (int x) {
    int r = x;
    st[top = 1] = r;
    while (nroot (r)) st[++ top] = r = fa[r];
    while (top) pushdown (st[top --]);
    while (nroot (x)) {
        int y = fa[x], z = fa[y];
        if (nroot (y)) 
            rotate (ident (x, y) ^ ident (y, z) ? x : y);
        rotate (x);
    }
    pushup (x);
}
inline void access (int x) {
    for (int y = 0; x; y = x, x = fa[y] = find(fa[x]))
        splay (x), rs(x) = y, pushup (x);
}
inline void makeroot (int x) {
    access (x);
    splay (x);
    pushrev (x);
}
inline int findroot (int x) {
    access (x), splay (x);
    while (ls(x)) pushdown (x), x = ls(x);
    splay (x);
    return x;
}
inline void split (int x, int y) {
    makeroot (y);
    access (x);
    splay (x);
}
inline void del (int x, int y) {
    if (! x) return;
    f[x] = y;
    del (ls(x), y);
    del (rs(x), y);
}
inline void merge (int x, int y) {
    if (x == y) return ;
    makeroot (x);
    if (findroot (y) != x) {
        fa[x] = y;
        return ;
    }
    del (rs(x), x);
    rs(x) = 0, pushup(x);
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n, m, cnt, x, y, tot;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) siz[i] = 1, f[i] = i;
    for (int i = 1; i <= m; i ++) {
        cin >> x >> y;
        if (x > y) swap (x, y);
        e[i] = {x, y};
    }
    sort (e + 1, e + m + 1);
    for (cnt = 1; cin >> op[cnt] && op[cnt] != -1; cnt ++) {
        cin >> x >> y;
        if (! op[cnt]) {
            if (x > y) swap (x, y);
            vis[lower_bound (e + 1, e + 1 + m, (node){x, y}) - e] = 1;
        }
        a[cnt] = x, b[cnt] = y;
    }
    for (int i = 1; i <= m; i ++) 
        if (! vis[i]) merge (find(e[i].x), find(e[i].y));
    for (cnt --, tot = 0; cnt; cnt --) {
        x = find(a[cnt]), y = find(b[cnt]);
        if (op[cnt]) split (x, y), ans[++ tot] = siz[x] - 1;
        else merge (x, y);
    }
    while (tot) cout << ans[tot --] << endl;
    return 0;
}

2. Title Link: P4172 [WC2006] Water Pipeline Director

Ideas: L C T LCT LCT offline resolution, time complexity O ( n l o g   n ) O(nlog\ n) O(nlog n). We find deleting edges difficult to achieve, so we process all the queries upside down and deleting edges becomes adding edges. Then query the minimum value of the maximum value on all paths. It is not difficult to find that you want to maintain the minimum spanning tree of this graph. Then you can directly query the maximum value on the tree path. You can use L C T LCT LCT does. This translates the problem into dynamic maintenance of the minimum spanning tree. The difficulty is easier than the previous one.

#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define re register
#define endl '\n'

using namespace std;

const int MOD = 998244353;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double Pi = acos(-1.0);
const int N = 1e3 + 5, M = 2e5 + 5;

#define ls(x) (ch[x][0])
#define rs(x) (ch[x][1])

int n, m, qur;
map<pair<int, int>, int> id;
struct edge { int u, v, w; } e[M];
struct que { int op, u, v, flag; } q[M];
auto cmp = [](edge a, edge b)->bool{return a.w < b.w;};
int fa[M], ch[M][2];
int mx[M], val[M], ans[M];
bool rev[M], vis[M];
inline bool isroot (int x) { return ls(fa[x]) != x && rs(fa[x]) != x; }
inline void pushup (int x) {
    mx[x] = val[x];
    if (e[mx[x]].w < e[mx[ls(x)]].w) mx[x] = mx[ls(x)];
    if (e[mx[x]].w < e[mx[rs(x)]].w) mx[x] = mx[rs(x)]; 
}
inline void pushrev (int x) {
    swap (ls(x), rs(x));
    rev[x] ^= 1;
}
inline void pushdown (int x) {
    if (rev[x]) {
        if (ls(x)) pushrev (ls(x));
        if (rs(x)) pushrev (rs(x));
        rev[x] = 0;
    }
}
int st[M], top;
inline void rotate (int x) {
    int y = fa[x], z = fa[y], k = rs(y) == x;
    if (! isroot (y)) ch[z][rs(z) == y] = x;
    ch[y][k] = ch[x][k ^ 1], ch[x][k ^ 1] = y;
    if (ch[y][k]) fa[ch[y][k]] = y;
    fa[x] = z, fa[y] = x;
    pushup (y), pushup (x);
}
inline void splay (int x) {
    int r = x;
    st[top = 1] = r;
    while (! isroot (r)) st[++ top] = r = fa[r];
    while (top) pushdown (st[top --]);
    while (! isroot (x)) {
        int y = fa[x], z = fa[y];
        if (! isroot (y))
            rotate ((rs(y) == x) ^ (rs(z) == y) ? x : y);
        rotate (x);
    }
    pushup (x);
}
inline void access (int x) { 
    for (int y = 0; x; x = fa[y = x])
        splay (x), rs(x) = y, pushup (x);
}
inline void makeroot (int x) { access (x), splay (x), pushrev (x); }
inline void split (int x, int y) { makeroot (x), access (y), splay (y); }
inline void link (int x, int y) { makeroot (x), fa[x] = y; }
inline void cut (int x, int y) { split (x, y), ls(y) = fa[x] = 0; }
inline int findroot (int x) { 
    access (x), splay (x);
    while (ls(x)) pushdown (x), x = ls(x);
    return x;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m >> qur, e[0].w = 0;
    for (int i = 1; i <= m; i ++) {
        cin >> e[i].u >> e[i].v >> e[i].w;
        if (e[i].u > e[i].v) swap (e[i].u, e[i].v);
    } 
    for (int i = 1; i <= n; i ++) val[i] = mx[i] = 0;
    for (int i = 1; i <= m; i ++) val[i + n] = mx[i + n] = i;
    sort (e + 1, e + 1 + m, cmp);
    for (int i = 1; i <= m; i ++) id[make_pair(e[i].u, e[i].v)] = i;
    for (int i = 1; i <= qur; i ++) {
        cin >> q[i].op >> q[i].u >> q[i].v;
        if (q[i].u > q[i].v) swap (q[i].u, q[i].v);
        if (q[i].op == 2) {
            q[i].flag = id[make_pair(q[i].u, q[i].v)];
            vis[q[i].flag] = true;
        }
    }
    
    for (int i = 1; i <= m; i ++) {
        if (vis[i]) continue;
        int u = e[i].u, v = e[i].v;
        if (findroot (u) == findroot (v)) continue;
        link (u, i + n), link (v, i + n);
    }
    for (int i = qur; i >= 1; i --) {
        int u = q[i].u, v = q[i].v;
        split (u, v);
        if (q[i].op == 1) {
            ans[i] = e[mx[v]].w;
        }else {
            int t = q[i].flag, d = mx[v];
            if (e[t].w < e[d].w) {
                cut (e[d].u, d + n), cut (e[d].v, d + n);
                link (u, t + n), link (v, t + n);
            }
        }
    }
    for (int i = 1; i <= qur; i ++) 
        if (q[i].op == 1) cout << ans[i] << endl;
    return 0;
}

3. Title Link: P2387 [NOI2014] Magic Forest

Ideas: L C T LCT LCT Solution, Time Complexity O ( n l o g   n ) O(nlog\ n) O(nlog n). Direct solution is more troublesome. We consider following the a i a_i ai Sorts each edge for the keyword and dynamically adds each edge in order so that we fix it each time a i a_i ai, using L C T LCT LCT Maintenance b i b_i The minimum of the maximum value of bi. All three of the questions here use a technique to convert edge rights into point rights. We'll look at the L C T LCT LCT is understood as a point. We insert two edges and one point to insert an edge. Now our problem becomes a problem of solving loops, so let's consider greed, and suppose we want to connect now ( u , v ) (u, v) (u,v), but u u u and v v There is already a path between v. This must be done at u u u to v v Select an edge in v's path to disconnect. Since the operation requires the least cost, the u u u to v v In v's path, select an edge with the largest edge weight to disconnect and then connect to the edge ( u , v ) (u, v) (u,v), of course, these are all in u u u to v v If v is already connected, we can connect it directly when disconnected.

#include <bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define re register
#define endl '\n'

using namespace std;

const int MOD = 998244353;
const int inf = 0x3f3f3f3f;
const double eps = 1e-8;
const double Pi = acos(-1.0);
const int N = 2e5 + 5;

#define ls(x) (ch[x][0])
#define rs(x) (ch[x][1])

int n, m;
struct edge { int x, y, a, b; } e[N];
auto cmp = [](edge u, edge v)->bool{ return u.a < v.a; };
int fa[N], ch[N][2], mx[N], val[N];
bool rev[N];

inline bool isroot (int x) { return ls(fa[x])!=x && rs(fa[x])!=x; }
inline void pushrev (int x) {
    swap (ls(x), rs(x));
    rev[x] ^= 1;
}
inline void pushdown (int x) {
    if (rev[x]) {
        if (ls(x)) pushrev (ls(x));
        if (rs(x)) pushrev (rs(x));
        rev[x] = 0;
    }
}
inline void pushup (int x) {
    mx[x] = val[x];
    if (e[mx[x]].b < e[mx[ls(x)]].b) mx[x] = mx[ls(x)];
    if (e[mx[x]].b < e[mx[rs(x)]].b) mx[x] = mx[rs(x)];
}
inline void rotate (int x) {
    int y = fa[x], z = fa[y], k = rs(y) == x;
    if (! isroot (y)) ch[z][rs(z) == y] = x;
    ch[y][k] = ch[x][k ^ 1], ch[x][k ^ 1] = y;
    if (ch[y][k]) fa[ch[y][k]] = y;
    fa[x] = z, fa[y] = x;
    pushup (y), pushup (x);
}
int st[N], top;
inline void splay (int x) {
    int r = x;
    st[top = 1] = r;
    while (! isroot (r)) st[++ top] = r = fa[r];
    while (top) pushdown (st[top --]);
    while (! isroot (x)) {
        int y = fa[x], z = fa[y];
        if (! isroot (y)) 
            rotate ((rs(y) == x) ^ (rs(z) == y) ? x : y);
        rotate (x);
    }
    pushup (x);
}
inline void access (int x) {
    for (int y = 0; x; x = fa[y = x]) 
        splay (x), rs(x) = y, pushup (x);
}
inline void makeroot (int x) { access (x), splay (x), pushrev (x); }
inline void split (int x, int y) { makeroot (x), access (y), splay (y); }
inline void link (int x, int y) { makeroot (x), fa[x] = y; }
inline void cut (int x, int y) { split (x, y), fa[x] = ls(y) = 0; }
inline int findroot (int x) {
    access (x), splay (x);
    while (ls(x)) pushdown (x), x = ls(x);
    return x;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i ++) 
        cin >> e[i].x >> e[i].y >> e[i].a >> e[i].b;
    sort (e + 1, e + 1 + m, cmp);
    for (int i = 1; i <= n; i ++) mx[i] = val[i] = 0;
    for (int i = 1; i <= m; i ++) mx[i + n] = val[i + n] = i;
    int ans = inf;
    for (int i = 1; i <= m; i ++) {
        int u = e[i].x, v = e[i].y;
        if (findroot (u) == findroot (v)) {
            split (u, v);
            int t = mx[v];
            if (e[i].b < e[t].b) {
                cut (e[t].x, t + n), cut (e[t].y, t + n);
                link (u, i + n), link (v, i + n);
            }
        }else link (u, i + n), link (v, i + n);
        split (1, n);
        if (findroot (1) == findroot (n)) 
            ans = min (ans, e[i].a + e[mx[n]].b);
    }
    if (ans == inf) ans = -1;
    cout << ans << endl;
    return 0;
}