直接建反边暴力 复杂度分析见https://blog.csdn.net/Izumi_Hanako/article/details/101267502

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = ;
ll out[MAXN], in[MAXN];
vector<int> G[MAXN];
int main() {
int n, m;
scanf("%d %d", &n, &m);
for (int i = ; 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 = ;
for (int i = ; 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] = ;
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 ;
}

最新文章

  1. java的动态代理机制详解
  2. git push命令
  3. JSLint JavaScript代码质量审查工具汉化中文版隆重发布
  4. Ubuntu 启动黑屏解决
  5. Linux01--文件管理,常用命令 权限管理
  6. JQuery操作元素的属性与样式及位置 复制代码
  7. 【★】深入BGP原理和思想【第一部】
  8. oracle安装时,条件检查不通过解决办法
  9. 51 nod 1297 管理二叉树
  10. ejabberd开发和部署
  11. C#实现联通短信Sgip协议程序源码
  12. Firefox下载附件乱码的解决办法
  13. python面试题--数据类型
  14. 1.4 Chrome浏览器
  15. UX设计秘诀之注册表单设计,细节决定成败
  16. HTTP 协议入门-笔记
  17. html5 的localstorage
  18. 在VMware中设置CentOS7的网络
  19. PIP安装时报The repository located at pypi.douban.com is not a trusted or secure host and is being ignore
  20. UnicodeEncodeError: &#39;ascii&#39; codec can&#39;t encode character u&#39;\xe9&#39; in position 7: ordinal not in range(128) [duplicate]

热门文章

  1. Git速成学习第四课:解决冲突
  2. C#实现隐藏手机号、邮箱、姓名等敏感信息扩展方法
  3. ZoomEye
  4. [LuoguP2157][SDOI2009]学校食堂_状压dp
  5. Linux下文件搜索、查找、查看命令
  6. sql server中实现mysql的find_in_set函数
  7. Linux下安装jdk中遇到的坑
  8. java中public protected friendly private作用域
  9. Spring4学习回顾之路11-AOP
  10. Thinking In Java 4th Chap3 操作符