CF 1795G Removal Sequences

給定一個無向圖，每個點有一個權值 $a_i$，節點 $i$ 可以被刪當且僅當 $i$ 的入度等於 $a_i$。要把整個圖刪光，存在許多刪除序列，問有多少個二元組 $(i, j)$，使得在某個刪除序列中，$i$ 比 $j$ 先刪，而在另一個刪除序列中，$j$ 比 $i$ 先刪。保證存在至少一個刪除序列。

求這樣的二元組比較麻煩，考慮求其反面，即刪除順序確定的二元組 $(i, j)$。

首先，在刪除的某個階段，容易證明所有滿足可刪條件的點不相鄰，換句話說，相鄰的點被刪的階段一定不同。因為如果存在相鄰，那麼刪除某一個，另一個入度減小，再也無法被刪，與條件矛盾。

所以我們可以先 bfs 求出每個點被刪除的階段 $lvl_i$，那麼對於相鄰的兩個點，$lvl$ 較小的一定在 $lvl$ 較大的之前被刪。考慮給每條邊定向，從 $lvl$ 較小的點指向較大的點，可以發現這個圖一定是一個有向無環圖。那麼 $i$ 在 $j$ 之前被刪就等價於可以從 $i$ 到達 $j$，問題就轉變成統計有向無環圖上的可達性統計。這個問題十分經典，令 $f(i, j)$ 表示第節點 $i$ 能否到達 $j$，則按照拓撲排序反向轉移即可。

然而這樣做是 $O(n^2)$ 的，無論記憶體還是時間上都無法通過。我們進行一些常數最佳化，將 $f(i)$ 定義成 uint64_t，並 64 個一組處理，假設當前是第 $k$ 組，那麼 $i$ 可以到 $j (64k \le j < 64k + 64)$ 就表示成 $(f(i) \operatorname{rightshift} (j - 64k)) \operatorname{and} 1 = 1$。這樣空間複雜度就是 $O(n)$ 的，每組的 $f$ 陣列可以迴圈利用。而時間複雜度並沒有最佳化，但常數優化了，可以通過此題。

程式碼很醜，推薦直接看題解。

struct graph
{
    vector<vector<int>> e;
    vector<int> indeg;
    graph(int n) : e(n), indeg(n) {}
};
 
struct directed_graph: public graph
{
    void add_edge(int u, int v)
    {
        // printf("add directed edge %d %d\n", u, v);
        e[u].emplace_back(v);
        indeg[v]++;
    }
    vector<int> sort()
    {
        int n = e.size();
        vector<int> res;
        res.reserve(n);
        std::queue<int> q;
        for (int i = 0; i < n; i++) {
            if (indeg[i] == 0) {
                q.emplace(i);
            }
        }
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            res.emplace_back(u);
            for (auto v : e[u]) {
                indeg[v]--;
                if (indeg[v] == 0) {
                    q.emplace(v);
                }
            }
        }
        return res;
    }
    long long count_approach()
    {
        int n = e.size();
        long long res = 0;
        auto seq = sort();
        // std::reverse(seq.begin(), seq.end());
        for (int i = 0; i * 64 < n; i++) {
            vector<uint64_t> f(n);
            int l = i * 64, r = (i + 1) * 64;
            for (auto j : seq) {
                if (l <= j && j < r) f[j] |= 1ull << (j - l);
                res += std::popcount(f[j]);
                for (auto v : e[j]) {
                    f[v] |= f[j];
                }
            }
        }
        return res;
    }
};
 
struct origin_graph : public graph
{
    vector<int> a;
    origin_graph(int n) : graph(n), a(n) {}
    void read(int m)
    {
        int n = e.size();
        for (auto &i : a) cin >> i;
        for (int i = 0; i < m; i++)
        {
            int u, v;
            cin >> u >> v;
            add_edge(u - 1, v - 1);
        }
    }
    void add_edge(int u, int v)
    {
        e[u].emplace_back(v);
        e[v].emplace_back(u);
        indeg[u]++;
        indeg[v]++;
    }
    directed_graph bfs()
    {
        int n = e.size();
        directed_graph res(n);
        vector<int> lvl(n);
        std::queue<std::pair<int, int>> q;
        for (int i = 0; i < n; i++) {
            if (indeg[i] == a[i]) {
                q.emplace(i, 0);
            }
        }
        while (!q.empty())
        {
            auto [u, l] = q.front();
            q.pop();
            lvl[u] = l;
            for (auto v : e[u]) {
                indeg[u]--;
                indeg[v]--;
                if (indeg[v] == a[v]) {
                    q.emplace(v, l + 1);
                }
            }
        }
        for (int i = 0; i < n; i++) {
            for (auto j : e[i]) {
                if (lvl[i] > lvl[j]) res.add_edge(i, j);
            }
        }
        return res;
    }
};
 
void solve()
{
    int n, m;
    cin >> n >> m;
    origin_graph g(n);
    g.read(m);
    auto ng = g.bfs();
    cout << (long long)n * (n - 1) / 2 + n - ng.count_approach() << endl;
}