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 ;
}

最新文章

  1. Solr4.10.3安装配置
  2. 为什么更喜欢Outlook,而不是Gmail
  3. winform listview控件、容器控件
  4. Echarts学习笔记之饼图
  5. Android实现圆形图片
  6. sqlhelper sqlparameter 实现增删改查
  7. TYVJ 1014 乘法游戏
  8. 动画(Animation) 、 高级动画(Core Animation)
  9. MySql5.5忘记root密码的解决方法
  10. [转] c和python利用setsockopt获得端口重用
  11. 无线通信技术协议-6LoWPAN
  12. 转发:[Python]内存管理
  13. 将多个图片整合到一张图片中再用CSS 进行网页背景定位
  14. spring Cache注解详解
  15. 转载 JavaScript的函数声明与函数表达式的区别
  16. plsql developer日期类型数据格式不对如何设置?
  17. 论文笔记:Show, Attend and Tell: Neural Image Caption Generation with Visual Attention
  18. java 二维数组的行列长度
  19. CentOS下部署Jupyter
  20. 详解SID之终结篇

热门文章

  1. 常用sql语句整理[MySql]
  2. mysql 查询及 删除表中重复数据
  3. s-2、charles 入门
  4. gitbook一仓库多本书持续化部署
  5. 【Linux相识相知】bash的特性
  6. WCF寄宿在C#控制台,并用命令行启动
  7. JavaScript typeof运算符和数据类型
  8. 破解jar包5步搞定,jira7.9.2操作成功,附github代码库
  9. XML入门介绍(什么是XML及XML格式)
  10. 关于Activity