题意翻译

在\(Byteotia\)有\(n\)个城镇。一些城镇之间由无向边连接。在城镇外没有十字路口，尽管可能有桥，隧道或者高架公路（反正不考虑这些）。每两个城镇之间至多只有一条直接连接的道路。人们可以从任意一个城镇直接或间接到达另一个城镇。每个城镇都有一个公民，他们被孤独所困扰。事实证明，每个公民都想拜访其他所有公民一次（在主人所在的城镇）。所以，一共会有\(n*（n-1）\)次拜访。

不幸的是，一个程序员总罢工正在进行中，那些程序员迫切要求购买某个软件。

作为抗议行动，程序员们计划封锁一些城镇，阻止人们进入，离开或者路过那里。

正如我们所说，他们正在讨论选择哪些城镇会导致最严重的后果。

编写一个程序：

读入\(Byteotia\)的道路系统，对于每个被决定的城镇，如果它被封锁，有多少访问不会发生，输出结果。

输入输出格式

第一行读入\(n，m\)，分别是城镇数目和道路数目

城镇编号\(1~n\)

接下来\(m\)行每行两个数字\(a,b\)，表示\(a\)和\(b\)之间有有一条无向边

输出\(n\)行，每行一个数字，为第i个城镇被锁时不能发生的访问的数量。

输入输出格式

输入格式：

In the first line of the standard input there are two positive integers: \(n\) and \(m\) (\(1\le n\le 100000\) , \(1\le m\le 500 000\)) denoting the number of towns and roads, respectively.

The towns are numbered from \(1\) to \(n\).

The following mm lines contain descriptions of the roads.

Each line contains two integers \(a\) and \(b\) (\(1\le a<b\le n\)) and denotes a direct road between towns numbered \(a\) and \(b\).

输出格式：

Your programme should write out exactly nn integers to the standard output, one number per line. The \(i^{th}\) line should contain the number of visits that could not take place if the programmers blocked the town no. \(i\).

输入输出样例

输入样例#1：

输出样例#1：

思路：利用tarjan查找割点的同时，我们可以找出该割点x去除后剩余的连通块（有两种情况，一种是在subTree(x)^x中，另一种是~subTree(x)）。就是一个在以x为根的子树内，一个不在。然后tarjan过程中乘法原理记录答案。

代码：

#include<cstdio>
#include<algorithm>
#include<cctype>
#define ll long long
#define maxn 100007
using namespace std;
ll n,m,num,cnt,head[maxn],dfn[maxn],low[maxn],size[maxn];
ll zrj[maxn];
inline ll qread() {
  char c=getchar();ll num=0,f=1;
  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
  for(;isdigit(c);c=getchar()) num=num*10+c-'0';
  return num*f;
}
struct node{
  ll v,nxt;
}e[1000007];
inline void ct(ll u, ll v) {
  e[++num].v=v;
  e[num].nxt=head[u];
  head[u]=num;
}
void tarjan(ll u) {
  ll res=0;
  size[u]=1;
  dfn[u]=low[u]=++cnt;
  for(ll i=head[u];i;i=e[i].nxt) {
    ll v=e[i].v;
    if(!dfn[v]) {
      tarjan(v);size[u]+=size[v];
      low[u]=min(low[v],low[u]);
      if(low[v]>=dfn[u]) zrj[u]+=size[v]*(n-size[v]),res+=size[v];
    }
    low[u]=min(low[u],dfn[v]);
  }
  zrj[u]+=(n-res-1)*(res+1)+n-1;
}
int main() {
  n=qread(),m=qread();
  for(ll i=1,u,v;i<=m;++i) {
    u=qread(),v=qread();
    ct(u,v);ct(v,u);
  }
  for(ll i=1;i<=n;++i) if(!dfn[i]) tarjan(i);
  for(ll i=1;i<=n;++i) printf("%lld\n",zrj[i]);
  return 0;
}

P3469 [POI2008]BLO-Blockade

题意翻译

输入输出格式

输入输出格式

输入输出样例