【洛谷P3469】[POI2008]BLO-Blockade
2024-08-27 15:10:23
BLO-Blockade
若一个点为割点:统计出每个子树的大小,两两相乘再相加,
再加上n-1,为这个点与其他点的拜访数,
因为拜访是互相的,最后再乘二即可
若一个点不是割点:只有(n-1)*2次拜访会受影响
#include<cstdio>
#define LL long long
#define N 100010
#define M 1000010
#define min(a,b) ((a)<(b)?(a):(b))
int n,m,dfn[N],low[N],size[N],cnt;
LL ans[N];
const int ch_top=4e7+;
char ch[ch_top],*now_r=ch-,*now_w=ch-;
inline int read(){
while(*++now_r<'');
register int x=*now_r-'';
while(*++now_r>='')x=x*+*now_r-'';
return x;
}
inline void write ( LL x ) {
static char st[] ; static int top ;
if ( x < ) *++now_w = '-' , x *= - ;
while( st[++top] = x % ^ , x /= ) ;
while( *++now_w = st[top] , --top );
*++now_w = '\n' ;
}
int Head[N],num;
struct NODE{
int to,next;
} e[M];
void Tarjan(int u){
dfn[u]=low[u]=++cnt;
size[u]=; int t=;
for(int i=Head[u];i;i=e[i].next){
int v=e[i].to;
if(!dfn[v]){
Tarjan(v);
size[u]+=size[v];
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
ans[u]+=(LL)t*size[v];
t+=size[v];
}
}
else low[u]=min(low[u],dfn[v]);
}
if(n-t->) ans[u]+=(LL)(n-t-)*t;
}
int main()
{ fread(ch,,ch_top,stdin);
n=read(); m=read();
int x,y;
for(int i=;i<=m;i++){
x=read(); y=read();
e[++num].to=y;
e[num].next=Head[x];
Head[x]=num;
e[++num].to=x;
e[num].next=Head[y];
Head[y]=num;
}
Tarjan();
for(int i=;i<=n;i++)
write((ans[i]+n-)<<);
fwrite(ch,,now_w-ch,stdout);
return ;
}
最新文章
- Solr4.10.3安装配置
- 为什么更喜欢Outlook,而不是Gmail
- winform listview控件、容器控件
- Echarts学习笔记之饼图
- Android实现圆形图片
- sqlhelper sqlparameter 实现增删改查
- TYVJ 1014 乘法游戏
- 动画(Animation) 、 高级动画(Core Animation)
- MySql5.5忘记root密码的解决方法
- [转] c和python利用setsockopt获得端口重用
- 无线通信技术协议-6LoWPAN
- 转发:[Python]内存管理
- 将多个图片整合到一张图片中再用CSS 进行网页背景定位
- spring Cache注解详解
- 转载 JavaScript的函数声明与函数表达式的区别
- plsql developer日期类型数据格式不对如何设置?
- 论文笔记:Show, Attend and Tell: Neural Image Caption Generation with Visual Attention
- java 二维数组的行列长度
- CentOS下部署Jupyter
- 详解SID之终结篇