题目

有一个 $n$ 个点的图,初始没有边。
有 $q$ 个操作,分为 $3$ 种,具体如下:

  • 1 u v 表示在 $u,v$ 之间连一条无向边。
  • 2 u v 表示求 $u,v$ 间的割边数量。
  • 3 u v 表示求 $u,v$ 间的割点数量。

强制在线。

$1\le n\le 10^5$,$1\le q\le 3\times 10^5$.

分析

维护边双

边双可以用并查集和树状数组维护,当然也可以用 LCT 维护。

连接属于同一连通块的两点相当于把这些点上的边都设为不是割边(显然你新加入的边也不是割边,所以无需加到树上),所以只需要把边拆成点,然后维护一个区间赋值的标记就好了。(并查集并不需要拆点,因为缩点相当于删边,但是这里必须拆点,因为删点可能会删到无辜的点)

维护点双

点双就比较麻烦了,我们考虑动态维护圆方树,对于一个新连的边 $(u,v)$,我们 Split 出 $u\to v$ 这条路径,然后暴力遍历整个路径,把其上所有边全部断掉,然后再建一个新点表示一个点双,把路径上的所有点连接到这个点双上。

这样统计答案的时候,我们只需要计算 $u\to v$ 这条路径上表示原图上的点的点的个数就好了。

我们可以发现,在每次操作我们新增一个新点的同时,旧的表示点双的点一定会被连到这个点双上,这使得 $u$ 到它所在的点双的距离永远不超过 $2$,所以每次操作点到点双之间对时间复杂度的贡献都是常数,只有点双的合并对时间复杂度有非常数的贡献,而点双的合并总共最多会进行 $\mathcal O(n)$ 次,故时间复杂度仍是 $\mathcal O(n\log n)$ 的。

代码

const int kN = 4e5 + 5, kInf = 0x3f3f3f3f;

struct LCT {
    struct Node {
        int val, siz, fa, ch[2];
        bool tag, rev;
    } tr[kN];
    inline bool Pos(int x) { return ch(fa(x), 1) == x; }
    inline bool IsRoot(int x) { return !x || (ch(fa(x), 0) != x && ch(fa(x), 1) != x); }
    inline void Update(int x) {
        siz(x) = siz(ch(x, 0)) + siz(ch(x, 1)) + val(x);
    }
    inline void PushRev(int x) {
        if(rev(x)) {
            rev(x) = 0;
            std::swap(ch(ch(x, 0), 0), ch(ch(x, 0), 1));
            std::swap(ch(ch(x, 1), 0), ch(ch(x, 1), 1));
            rev(ch(x, 0)) ^= 1; rev(ch(x, 1)) ^= 1;
        }
    }
    inline void PushTag(int x) {
        if(tag(x)) {
            tag(x) = 0;
            tag(ch(x, 0)) = tag(ch(x, 1)) = 1;
            siz(ch(x, 0)) = siz(ch(x, 1)) = 0;
            val(ch(x, 0)) = val(ch(x, 1)) = 0;
        }
    }
    void ClearTag(int x) {
        if(!IsRoot(x)) ClearTag(fa(x));
        PushRev(x); PushTag(x);
    }
    void Rotate(int x) {
        int y = fa(x), z = fa(y), p = Pos(x);
        if(!IsRoot(y)) ch(z, Pos(y)) = x;
        fa(x) = z; fa(y) = x; fa(ch(x, p ^ 1)) = y;
        ch(y, p) = ch(x, p ^ 1); ch(x, p ^ 1) = y;
        Update(y); Update(x);
    }
    void Splay(int x) {
        ClearTag(x);
        for(; !IsRoot(x); Rotate(x))
            if(!IsRoot(fa(x))) Rotate(Pos(fa(x)) == Pos(x) ? fa(x) : x);
    }
    int Access(int x) {
        int p;
        for(p = 0; x; p = x, x = fa(x)) {
            Splay(x); ch(x, 1) = p; Update(x);
        }
        return p;
    }
    void MakeRoot(int x) {
        rev(x = Access(x)) ^= 1;
        std::swap(ch(x, 0), ch(x, 1));
    }
    void Split(int x, int y) {
        MakeRoot(x); Access(y); Splay(y);
    }
    int Find(int x) {
        Access(x); Splay(x);
        for(; ch(x, 0); x = ch(x, 0)) PushRev(x);
        Splay(x);
        return x;
    }
    void Link(int x, int y) {
        MakeRoot(x); Splay(x); fa(x) = y;
    }
    void Cut(int x, int y) {
        Split(x, y); fa(x) = ch(y, 0) = 0; Update(y);
    }
    void Modify(int x, int y) {
        Split(x, y); siz(y) = val(y) = 0; tag(y) = 1;
    }
    void Dfs(int x, std::vector <int> &P) {
        PushRev(x); PushTag(x);
        if(ch(x, 0)) Dfs(ch(x, 0), P);
        P.push_back(x);
        if(ch(x, 1)) Dfs(ch(x, 1), P);
    }
    void GetPath(int x, int y, std::vector <int> &P) {
        P.clear(); Split(x, y); Dfs(y, P);
    }
} ebc, pbc;

int n, q, pbc_cnt = 0, m_cnt = 0;
std::vector <int> tmp;
void Link(int u, int v) {
    if(ebc.Find(u) != ebc.Find(v)) {
        ++m_cnt;
        ebc.Link(u, n + m_cnt);
        ebc.Link(v, n + m_cnt);
        pbc.Link(u, v);
    } else {
        ebc.Modify(u, v);
        pbc.GetPath(u, v, tmp);
        for(int i = 1; i < tmp.size(); ++i)
            pbc.Cut(tmp[i], tmp[i - 1]);
        ++pbc_cnt;
        for(int i = 0; i < tmp.size(); ++i)
            pbc.Link(tmp[i], n + pbc_cnt);
    }
}
int EbcQuery(int u, int v) {
    if(u == v) return 0;
    if(ebc.Find(u) != ebc.Find(v))
        return -1;
    ebc.Split(u, v);
    return ebc.siz(v);
}
int PbcQuery(int u, int v) {
    if(u == v) return 1;
    if(pbc.Find(u) != pbc.Find(v))
        return -1;
    pbc.Split(u, v);
    return pbc.siz(v);
}

int main() { 
    int lst_ans = 0, ans;
    rd(n, q);
    for(int i = 1; i <= n; ++i)
        pbc.val(i) = 1;
    for(int i = 1; i <= q; ++i)
        ebc.val(n + i) = 1;
    for(int i = 1; i <= q; ++i)  {
        int opt, u, v; rd(opt, u, v);
        u ^= lst_ans; v ^= lst_ans;
        if(opt == 1) {
            Link(u, v);
        } else if(opt == 2) {
            printf("%d\n", ans = EbcQuery(u, v));
            if(ans != -1) lst_ans = ans;
        } else {
            printf("%d\n", ans = PbcQuery(u, v));
            if(ans != -1) lst_ans = ans;
        }
    }
    return 0;
}
最后修改:2021 年 02 月 01 日 01 : 24 PM