直接建反边暴力 复杂度分析见https://blog.csdn.net/Izumi_Hanako/article/details/101267502
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 100005; ll out[MAXN], in[MAXN]; vector<int> G[MAXN]; int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { int u, v; scanf("%d %d", &u, &v); if (u < v) { swap(u, v); } out[u]++, in[v]++; G[v].push_back(u); } ll ans = 0; for (int i = 1; i <= n; i++) { ans += out[i] * in[i]; } cout << ans << endl; int Q; scanf("%d", &Q); while (Q--) { int x; scanf("%d", &x); ans -= out[x] * in[x]; out[x] += G[x].size(), in[x] = 0; for (int v : G[x]) { ans -= out[v] * in[v]; out[v]--, in[v]++; ans += out[v] * in[v]; G[v].push_back(x); } G[x].clear(); cout << ans << endl; } return 0; }