我的思路：

一开始图就有可能不连通，设连通块的数量为 $t$​​，$i$ 号连通块内共有 $size(i)$ 个节点，则原图中不能互相到达的点对有 $\sum\limits_{i=1}^t size(i)\times(n-size(i))$。但这个结果是有序的，所以要 $\div2$​。

考虑删掉一条边后会增加多少。

1. 若边 $<u,v>$ 不是桥，那不会变；
2. 若 $<u,v>$ 是桥，设搜索树中 $subtree(x)$ 内共有 $siz(x)$ 个点，该连通块的根节点为 $root$，则删掉 $<u,v>$ 后会增加 $siz(v)\times(siz(root)-siz(v))$​ 组。

所以代码大概长这样：

#include <iostream>
#include <cstdio>
using namespace std;

const int MAXN = 1e6 + 5;

int n, m, q, cnt = 1, Time, rt, sum;
int head[MAXN], dfn[MAXN], low[MAXN], siz[MAXN], ans[MAXN];
bool bridge[MAXN << 1];

struct sid_shi
{
	int rt, v;
}akioi[MAXN << 1];

struct edge
{
	int to, nxt;
}e[MAXN << 1];

void add(int u, int v)
{
	e[++cnt] = edge{v, head[u]};
	head[u] = cnt;
}

void tarjan(int u, int in_edge)
{
	dfn[u] = low[u] = ++Time;
	siz[u] = 1;
	for (int i = head[u]; i; i = e[i].nxt)
	{
		int v = e[i].to;
		if (!dfn[v])
		{
			tarjan(v, i);
			low[u] = min(low[u], low[v]);
			siz[u] += siz[v];
			if (dfn[u] < low[v])
			{
				bridge[i] = bridge[i ^ 1] = true;
				akioi[i] = akioi[i ^ 1] = sid_shi{rt, v}; //siz(rt)还没更新完，先存着
			}
		}
		else if (i != (in_edge ^ 1))
		{
			low[u] = min(low[u], dfn[v]);
		}
	}
}

int main()
{
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1; i <= m; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		u++, v++;
		add(u, v);
		add(v, u);
	}
	for (int i = 1; i <= n; i++)
	{
		if (!dfn[i])
		{
			tarjan(rt = i, 0);
			sum = (sum + siz[rt] * (n - siz[rt]) % 1000) % 1000; //原图有多少对
		}
	}
	sum >>= 1;
	for (int i = 1; i <= m; i++)
	{
		if (bridge[i << 1])
		{
			ans[i] = siz[akioi[i << 1].v] * (siz[akioi[i << 1].rt] - siz[akioi[i << 1].v]) % 1000; //统一处理
		}
	}
	while (q--)
	{
		int x;
		scanf("%d", &x);
		x++;
		printf("%d\n", sum + ans[x]);
	}
	return 0;
}
/*
4 3 3
0 1
1 0
0 2
0
1
2
*/

然后学校 $\text{OJ}$ 上 $\text{WA30}\dots\dots$

各位大佬能帮忙康康思路有没有错吗？如果没错，那是不是代码错了？

thanks!