AHOI2005 航线规划

Ameiyo · 2019-07-24 15:57:34 · 个人记录

AHOI2005 航线规划

洛谷连接

先考虑没有删边的情况：

如果我们把所有的环都缩成点，那么整张图就变成了一棵树，环边都不可能是关键边，而树边可能是（要在两点间路径上），所以一开始直接点双（边双？）缩点，然后建一棵树直接 lca 询问两点间边数即可。

但是如果有了删边，那么每次删完边，图的形状都会发生或大或小的变化，那么（似乎 lct 可以？考试的时候想到了，但没学过 lct 嘤嘤嘤）就不好维护了。。。

这里我们仔细读题，发现题目给出了两个条件：

任何时候保证图连通

保证删掉的边不会加上

第一个条件告诉我们不用重构树。

第二个条件告诉我们没有相反操作，也就是说我们不需要维护 两种互相抵消的操作 。

这样，每个删掉的边的影响就是永久的，所以如果一开始把所有边都删掉，那么就是最后的情况。

考虑离线，发现在一棵树上，加入一条边会导致两点间路径上所有的边都不是关键边。

流程：

输入
构造出树（用没删掉的边）
把所有没删掉的边又不是树边的边加入（操作与加边一模一样）
倒着维护处答案

树上两点间路径设置（为 0 ）以及求和，重剖 + 线段树暴力。。。

也可以并查集 + dfs 序 + 树状数组维护。

（加边：一条边设为 0 后就与其父亲合并，之后每次直接用“蜗牛爬”LCA更新，并且其会对子树内的点往根上的权值和造成 -1 影响，用树状数组 + dfs 序，合并用并查集，查询直接找到 lca （注意这里不能用蜗牛爬！！！）然后加加减减就行）

代码

（并查集的可以看看 orangejuice9 的）

#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

#define ll long long
#define reg register
#define rep(i, a, b) for (reg int i = (a), i##end = (b); i <= i##end; ++i)
#define dep(i, a, b) for (reg int i = (a), i##end = (b); i >= i##end; --i)

template <typename _typer> inline _typer read() {
    _typer init = 0;
    char ch = getchar(), k = 0;
    for ( ; !isdigit(ch); ch = getchar()) k = (ch == '-');
    for ( ; isdigit(ch); ch = getchar())
        init = (init << 3) + (init << 1) + (ch ^ 48);
    return k ? -init : init;
}
const ll N = 40005, INF = 1e9;
const ll M = 100005;

int n, m, q;

struct EDGE {
    int to, nex;
} edge[N << 1], total[M];
int head[N], cntedge, mark[M], edgemark[M];
void Addedge(int u, int v) {
    edge[++cntedge] = (EDGE) { v, head[u] };
    head[u] = cntedge;
}

int Dep[N], Fa[N];
int Top[N], Siz[N], Son[N];
int Ldfn[N], Rdfn[N], cntDfs;
void Dfs1(int u, int fa) {
    Dep[u] = Dep[Fa[u] = fa] + 1;
    Siz[u] = 1, Son[u] = -1;
    for (int i = head[u], v; i; i = edge[i].nex) {
        v = edge[i].to;
        if (v == fa) continue;
        Dfs1(v, u);
        Siz[u] += Siz[v];
        if (Son[u] == -1 || Siz[v] > Siz[Son[u]]) Son[u] = v;
    }
}
void Dfs2(int u, int tp) {
    Top[u] = tp;
    Ldfn[u] = ++cntDfs;
    if (Son[u] != -1) Dfs2(Son[u], tp);
    for (int i = head[u], v; i; i = edge[i].nex) {
        v = edge[i].to;
        if (v == Fa[u] || v == Son[u]) continue;
        Dfs2(v, v);
    }
    Rdfn[u] = cntDfs;
}

int Sum[N << 2], tag[N << 2];
#define ls (p << 1)
#define rs (p << 1 | 1)
void Pushup(int p) {
    Sum[p] = Sum[ls] + Sum[rs];
}
void Pushdown(int p) {
    if (~tag[p]) {
        Sum[ls] = Sum[rs] = 0;
        tag[ls] = tag[rs] = 0;
        tag[p] = -1;
    }
}
void Built(int p, int l, int r) {
    tag[p] = -1, Sum[p] = r - l + 1;
    if (l == 1) --Sum[p];
    if (l == r) return ;
    int mid = (l + r) >> 1;
    Built(ls, l, mid); Built(rs, mid + 1, r);
}
void Upd(int p, int l, int r, int L, int R) {
    if (L > R) return ;
    if (L == l && r == R) {
        tag[p] = Sum[p] = 0;
        return ;
    }
    Pushdown(p);
    int mid = (l + r) >> 1;
    if (R <= mid) Upd(ls, l, mid, L, R);
    else if (L > mid) Upd(rs, mid + 1, r, L, R);
    else Upd(ls, l, mid, L, mid), Upd(rs, mid + 1, r, mid + 1, R);
    Pushup(p);
}
int Que(int p, int l, int r, int L, int R) {
    if (L > R) return 0;
    if (L == l && r == R) return Sum[p];
    Pushdown(p);
    int mid = (l + r) >> 1;
    if (R <= mid) return Que(ls, l, mid, L, R);
    if (L > mid) return Que(rs, mid + 1, r, L, R);
    return Que(ls, l, mid, L, mid) + Que(rs, mid + 1, r, mid + 1, R);
}

void Update(int x, int y) {
    for ( ; Top[x] != Top[y];
        Upd(1, 1, n, Ldfn[Top[y]], Ldfn[y]), y = Fa[Top[y]])
        if (Dep[Top[x]] > Dep[Top[y]]) swap(x, y);
    if (Dep[x] > Dep[y]) swap(x, y);
    Upd(1, 1, n, Ldfn[x] + 1, Ldfn[y]);
}
int Query(int x, int y) {
    int Ans = 0;
    for ( ; Top[x] != Top[y];
        Ans += Que(1, 1, n, Ldfn[Top[y]], Ldfn[y]), y = Fa[Top[y]])
        if (Dep[Top[x]] > Dep[Top[y]]) swap(x, y);
    if (Dep[x] > Dep[y]) swap(x, y);
    return (Ans += Que(1, 1, n, Ldfn[x] + 1, Ldfn[y]));
}

int fa[N], cnt;
struct QUERY {
    int opt, x, y, Ans;
} Q[N * 3];
struct QUESTION {
    int Find(int x) {
        return x == fa[x] ? x : fa[x] = Find(fa[x]);
    }
    bool Uni(int x, int y) {
        x = Find(x), y = Find(y);
        if (x != y) return fa[x] = y, --cnt, true;
        return false;
    }
    inline bool operator () (const EDGE &x, const EDGE &y) const {
        return x.to < y.to || (x.to == y.to && x.nex < y.nex);
    }
    void Work() {
        rep (i, 1, n) fa[i] = i;
        cnt = n;

        rep (i, 1, m) if (!mark[i]) if (Uni(total[i].to, total[i].nex)) {
            edgemark[i] = true;
            Addedge(total[i].to, total[i].nex);
            Addedge(total[i].nex, total[i].to);
        }

        Dfs1(1, 1); Dfs2(1, 1);
        Built(1, 1, n);

        rep (i, 1, m) if (!mark[i] && !edgemark[i])
            Update(total[i].to, total[i].nex);

        dep (i, q, 1) {
            if (Q[i].opt == 0) Update(Q[i].x, Q[i].y);
            else Q[i].Ans = Query(Q[i].x, Q[i].y);
        }

        rep (i, 1, q) if (Q[i].opt == 1) printf("%d\n", Q[i].Ans);
    }
} p100;

int main() {
    n = read<int>(), m = read<int>();
    rep (i, 1, m) {
        int x = read<int>(), y = read<int>();
        if (x > y) swap(x, y);
        total[i] = (EDGE) { x, y };
    }

    sort(total + 1, total + m + 1, QUESTION());

     int opt = read<int>();
     while (opt != -1) {
        int x = read<int>(), y = read<int>(), i = ++q;
        if (opt == 0) {
            if (x > y) swap(x, y);
            int k = lower_bound(total + 1, total + m + 1,
                                (EDGE) { x, y }, QUESTION()) - total;
            mark[k] = true;
            Q[i] = (QUERY) { opt, x, y, 0 };
        } else {
            Q[i] = (QUERY) { opt, x, y, 0 };
        }
        opt = read<int>();
    }

    p100.Work();
    return 0;
}