https://www.luogu.org/problem/P3469

题目就是说封锁一个点,会导致哪些点(对)连不通;

用tarjan求割点,如果这个点是割点,那么不能通行的点对数就是(乘法法则)儿子子树大小的相乘+n-1;

如果不是割点就是n-1;

#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=5e5+;
int pre[maxn*],last[maxn],other[maxn*],l;
int n,m;
void add(int x,int y)
{
l++;
pre[l]=last[x];
last[x]=l;
other[l]=y;
}
bool vis[maxn];
long long ans[maxn];
int dfn[maxn],cnt,low[maxn],siz[maxn],fa[maxn];
void dfs(int x)
{
dfn[x]=low[x]=++cnt;
vis[x]=;
siz[x]=;
int ss=;
for(int p=last[x];p;p=pre[p])
{
int v=other[p];
if(!vis[v])
{
fa[v]=x;
dfs(v);
siz[x]+=siz[v];
low[x]=min(low[x],low[v]);
if(low[v]>=dfn[x]&&fa[x]!=v)//该儿子节点不能绕过这个点到达上方节点
{
ans[x]+=(long long)ss*siz[v];//已经计算过的被封锁的儿子们乘上现在的
ss+=siz[v];//更新
}
}
else low[x]=min(low[x],dfn[v]);
}
ans[x]+=(long long )(n-);
ans[x]+=(long long )ss*(n-ss-);//被封锁的儿子乘上没有被封锁的
} int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);add(b,a);
}
dfs();
for(int i=;i<=n;i++)
{
printf("%lld\n",ans[i]*);//点对有序
}
return ;
}

最新文章

  1. html、canvas、视频灰度、反色
  2. Android成长日记-使用ToggleButton实现灯的开关
  3. 容易混淆的url src href
  4. Android 4.4KitKat AudioRecord 流程分析
  5. ActiveMQ(5.10.0) - Message Redelivery and DLQ Handling
  6. BBC票选出的100部最经典美国电影,你看过几部?
  7. 高放的python学习笔记之基本语法
  8. JS乘法口诀表(一行代码)
  9. 【外文翻译】 为什么我要写 getters 和setters
  10. Iframe父子窗口之间的跨域事件调用和传值
  11. FLP不可能性(FLP impossibility)
  12. Android+TensorFlow+CNN+MNIST 手写数字识别实现
  13. Sql函数笔记一、case when
  14. Docker 基本核心原理
  15. 10分钟轻松学会 Python turtle 绘图
  16. MongoDB(1)--简单介绍以及安装
  17. ZZNU 正约数之和 2094
  18. Vue.js 添加组件
  19. 【转】【Python】python使用urlopen/urlretrieve下载文件时出现403 forbidden的解决方法
  20. 用户体验要好,App动画得这么做

热门文章

  1. Http 与 Https区别
  2. 数据库入门(mySQL):创建数据库
  3. MySQL: Can’t connect to MySQL server on (111 “Connection refused”)
  4. Sharing is only supported for boot loader classes because bootstrap classpath has been appended
  5. Java字节码文件结构剖析
  6. PHP实现月份自动加1
  7. Python与数据库 sqlalchemy 建立声明层表对象的两种方式
  8. 2.session 简介
  9. IdentityServer(二)客户端授权模式
  10. linux实操_shell设置环境变量