思路与算法

迭代DFS求low与桥，记录各原连通分量大小。原本不连通的无序点对数为C(n,2)-ΣC(size,2)。删除非桥不增加；删除桥且子侧大小s、所属分量大小c时增加s(c-s)，查询输出总数模1000。

正确性说明

low判据等价树边下方没有绕回祖先的其他边，因此只有桥会使分量断开。桥断开后恰好一端在两侧的s(c-s)对新增不连通，其他原连通及不连通点对状态不变。

复杂度

读入、DFS与初始化O(N+M)，Q次查询O(Q)，总O(N+M+Q)时间，O(N+M)空间。

易错点

按边ID跳父边才能正确支持平行边，自环不是桥。原图可能不连通。计数先用64位，最后取模，不要把分量大小提前取模。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, Q;
    cin >> n >> m >> Q;
    vector<vector<pair<int, int>>> g(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back({b, i});
        g[b].push_back({a, i});
    }
    vector<int> dfn(n), low(n), sub(n, 1), par(n, -1), pe(n, -1), cur(n), comp(n), cut(m), rootSize;
    int timer = 0;
    for (int s = 0; s < n; s++)
        if (!dfn[s]) {
            int cid = rootSize.size();
            vector<int> st(1, s);
            dfn[s] = low[s] = ++timer;
            comp[s] = cid;
            while (!st.empty()) {
                int u = st.back();
                if (cur[u] < (int)g[u].size()) {
                    auto e = g[u][cur[u]++];
                    int v = e.first, id = e.second;
                    if (id == pe[u])
                        continue;
                    if (!dfn[v]) {
                        par[v] = u;
                        pe[v] = id;
                        comp[v] = cid;
                        dfn[v] = low[v] = ++timer;
                        st.push_back(v);
                    } else
                        low[u] = min(low[u], dfn[v]);
                } else {
                    st.pop_back();
                    if (par[u] >= 0) {
                        int p = par[u];
                        sub[p] += sub[u];
                        low[p] = min(low[p], low[u]);
                        if (low[u] > dfn[p])
                            cut[pe[u]] = sub[u];
                    }
                }
            }
            rootSize.push_back(sub[s]);
        }
    long long base = 1LL * n * (n - 1) / 2;
    for (int sz : rootSize)
        base -= 1LL * sz * (sz - 1) / 2;
    vector<long long> extra(m);
    for (int u = 0; u < n; u++)
        if (pe[u] >= 0 && cut[pe[u]])
            extra[pe[u]] = 1LL * sub[u] * (rootSize[comp[u]] - sub[u]);
    while (Q--) {
        int e;
        cin >> e;
        cout << (base + extra[e]) % 1000 << '\n';
    }
}