P3469 割点的应用
2024-09-05 03:46:49
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 ;
}
最新文章
- html、canvas、视频灰度、反色
- Android成长日记-使用ToggleButton实现灯的开关
- 容易混淆的url src href
- Android 4.4KitKat AudioRecord 流程分析
- ActiveMQ(5.10.0) - Message Redelivery and DLQ Handling
- BBC票选出的100部最经典美国电影,你看过几部?
- 高放的python学习笔记之基本语法
- JS乘法口诀表(一行代码)
- 【外文翻译】 为什么我要写 getters 和setters
- Iframe父子窗口之间的跨域事件调用和传值
- FLP不可能性(FLP impossibility)
- Android+TensorFlow+CNN+MNIST 手写数字识别实现
- Sql函数笔记一、case when
- Docker 基本核心原理
- 10分钟轻松学会 Python turtle 绘图
- MongoDB(1)--简单介绍以及安装
- ZZNU 正约数之和 2094
- Vue.js 添加组件
- 【转】【Python】python使用urlopen/urlretrieve下载文件时出现403 forbidden的解决方法
- 用户体验要好,App动画得这么做
热门文章
- Http 与 Https区别
- 数据库入门(mySQL):创建数据库
- MySQL: Can’t connect to MySQL server on (111 “Connection refused”)
- Sharing is only supported for boot loader classes because bootstrap classpath has been appended
- Java字节码文件结构剖析
- PHP实现月份自动加1
- Python与数据库 sqlalchemy 建立声明层表对象的两种方式
- 2.session 简介
- IdentityServer(二)客户端授权模式
- linux实操_shell设置环境变量