题目:https://www.lydsy.com/JudgeOnline/problem.php?id=1123

思路倒是有的,不就是个乘法原理吗,可是不会写...代码能力...

写了一堆麻麻烦烦乱七八糟的东西写不下去了,去看TJ...

原来是在 tarjan 里面就顺便算出来了啊!真是精妙!这就是构建出了一个 dfs 搜索树了呢;

码力还需多多提升...

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;
int const maxn=1e5+,maxm=5e5+;
int n,m,hd[maxn],ct,siz[maxn],dfn[maxn],low[maxn],tim;
ll ans[maxn];
struct N{
int to,nxt;
N(int t=,int n=):to(t),nxt(n) {}
}ed[maxm<<],edge[maxm<<];
void add(int x,int y){ed[++ct]=N(y,hd[x]); hd[x]=ct;}
void tarjan(int x,int f)
{
dfn[x]=low[x]=++tim;
ll t=; siz[x]=;//注意t是ll,否则下面算给ans时爆int
for(int i=hd[x],u;i;i=ed[i].nxt)
{
if((u=ed[i].to)==f)continue;
if(!dfn[u])
{
tarjan(u,x); siz[x]+=siz[u];
low[x]=min(low[x],low[u]);
if(low[u]>=dfn[x])ans[x]+=siz[u]*t,t+=siz[u];//t是割点的子树大小
}
else low[x]=min(low[x],dfn[u]);
}
ans[x]+=t*(n-t-);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=,x,y;i<=m;i++)
{
scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
tarjan(,);
for(int i=;i<=n;i++)printf("%lld\n",(ans[i]+n-)*);
return ;
}

最新文章

  1. session的生命周期
  2. 从xml中构建sqlSessionFactory
  3. 方程ax2+bx+c=0;一元二次方程。求根
  4. Swift实战-小QQ(第1章):QQ登录界面
  5. Start:at cnblogs firstDay
  6. Windows Live Writer教程及代码高亮工具
  7. 函数式宏定义用do...while(0)的好处
  8. Android自定义图形,图形的拼接、叠加、相容
  9. HDU 1520-Anniversary party(树形dp入门)
  10. (原创)fedora 17安装KVM虚拟机
  11. 改MAC地址
  12. linux下如何删除文件夹?
  13. BZOJ1004 HNOI2008 Cards Burnside、背包
  14. hdu-4507 吉哥系列故事——恨7不成妻 数位DP 状态转移分析/极限取模
  15. [LeetCode] 191. Number of 1 Bits ☆(位 1 的个数)
  16. ASP.NET前台代码绑定后台变量方法总结
  17. [LeetCode] 728. Self Dividing Numbers_Easy tag: Math
  18. CH4201 楼兰图腾
  19. ACP敏捷管理
  20. HDU4045_Machine scheduling

热门文章

  1. JS高级——扩展内置对象的方法
  2. CSS——background
  3. jsp 文件下载
  4. 2016.01.22 前端学习 HTML/CSS
  5. 阿里云ECS远程桌面连接失败
  6. strcmp 与 _tcscmp
  7. Django - 基于orm实现用户增删改查
  8. 18.match_phrase的用法
  9. emacs 定制进缩风格
  10. php 漏洞分析