• https://oi-wiki.org/graph/block-forest/#%E4%BE%8B%E9%A2%98
• https://codeforces.com/gym/102512/problem/A
• https://www.shuizilong.com/house/archives/spoj-9577-dynamic-tree-connectivity/
• https://www.shuizilong.com/house/archives/spoj-375-query-on-a-tree/

仙人掌

• https://codeforces.com/problemset/problem/231/E

LibreOJ #2587. 「APIO2018」铁人两项

巧妙的标号，设方点的权值为周围圆点的个数，圆点的权值为 -1，那么任意一个合法的 (s,f)，中间合法的 c 恰好等于它们在圆方树上路径的权值和。于是直接树 dp 即可。

Codeforces Round 278 (Div. 1) E. Tourists

圆方树后转化为 QTREE。
如果我们方点的权值记为所有周围圆点的最小值，那么修改圆点操作可能会影响 O(n) 个节点，
但是其实我们可以只考虑有根树，方点只记录孩子中圆点的最小值，那么操作就只会影响 O(1) 个节点了，
这样统计答案的时候，如果 lca 是方点，只要再向上取一个最小值即可。
这个技巧在 之前 也出现过。

Luogu P8456. 「SWTR-8」地地铁铁

• https://www.luogu.com.cn/problem/P8456

难点在于什么情况下两点之间同时存在白路径和黑路径，但不存在黑白路径。
这个题还需要找到每个双连通分量内的所有边，所以还需要开个边栈。

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(1e6) + 9, M = int(2e6) + 9;

int dfn[N], low[N]; stack<int> sta, sta_e; int nn;
int hd[N], suc[M], to[M];
int n; LL z;

namespace DSU{ // Disjoint Set Union
    int P[N], R[N], sz[N];
    inline void Make(int x){
        P[x] = x, R[x] = 0;
    }
    inline int Find(int x){
        return P[x] == x ? x : P[x] = Find(P[x]);
    }
    inline void Unionn(int x, int y){
        if (R[x] == R[y]) ++R[x];
        else if (R[x] < R[y]) swap(x, y);
        sz[x] += sz[y];
        P[y] = x;
    }
    inline void Union(int x, int y){
        x = Find(x), y = Find(y);
        if (x != y) Unionn(x, y);
    }
} //using namespace DSU;

inline LL C2(LL n) {
    return n*(n-1)/2;
}

struct Block_Cut_Tree {
    VI adj[N]; int fa[N], col[N];
    int n;

    void add_block(int u, int v, int r) {
        ++n; int b = ::n+n;
        adj[u].PB(b); fa[b] = u;
        do {
            u = sta.top(); sta.pop();
            adj[b].PB(u);
        } while (u^v);

        int i, c; map<int, int> mask;
        do {
            i = sta_e.top(), sta_e.pop();
            u = to[i^1], v = to[i]; if (u < 0) u = -u, v = -v, c = 2; else c = 1;
            col[b] |= c; mask[u] |= c; mask[v] |= c;
        } while (r^i);

        if (col[b] == 3) {
            int cnt = 0; for (auto t: mask) if (t.se == 3) {
                if (++cnt > 2) break;
            }
            if (cnt == 2) --z;
        }
    }

    LL calc(int c) {
        using namespace DSU;
        int nn = ::n+n;
        REP_1(i, nn) Make(i);
        REP_1(i, ::n) sz[i] = 1;
        REP_1(i, n) sz[::n+i] = 0;

        FOR_1(b, ::n+1, nn) if (col[b] == c) {
            Union(b, fa[b]);
            for (auto u: adj[b]) Union(b, u);
        }

        LL z = 0; REP_1(i, nn) if (Find(i) == i) z += C2(sz[i]);
        return z;
    }
} bct;

void tarjan(int u = 1, int r = 0) {

    dfn[u] = low[u] = ++nn;
    sta.push(u);

    REP_G(i, u) if (i^r) {
        int v = abs(to[i]);
        if (dfn[v]) {
            if (dfn[u] < dfn[v]) continue;
            sta_e.push(i);
            checkMin(low[u], dfn[v]);
        } else {
            sta_e.push(i); tarjan(v, i^1);
            checkMin(low[u], low[v]);
            if (dfn[u] <= low[v]) { // find a cut!
                bct.add_block(u, v, i);
            }
        }
    }
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif

    RD(); int m; RD(n, m);

    for (int i=2;i<=2*m;) {
        int x, y; bool c; RD(x, y); c = RC() == 'd';
        suc[i] = hd[x], hd[x] = i, to[i] = c ? -y : y; ++i;
        suc[i] = hd[y], hd[y] = i, to[i] = c ? -x : x; ++i;
    }

    z = C2(n); tarjan();
    z -= bct.calc(1) + bct.calc(2);
    cout << z << endl;
}

Posted by xiaodao
Category: 日常