BLO-Blockade[POI2008]

AK-dream

发布于：2020年7月31日

题目描述

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

不幸的是，一个程序员总罢工正在进行中，那些程序员迫切要求购买某个软件。作为抗议行动，程序员们计划封锁一些城镇，阻止人们进入，离开或者路过那里。正如我们所说，他们正在讨论选择哪些城镇会导致最严重的后果。

编写一个程序：

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

输入格式

第一行读入$n，m (1\le n\le 100\ 000, 1\le m\le 500\ 000)$，分别是城镇数目和道路数目

城镇编号$1\sim n$

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

输出格式

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

题解

显然，只有被封锁的点为割点时，才会出现无法访问的情况

所以求出所有点双连通分量，对原图建出圆方树，只需要找出对于每个非叶子的圆点(原图中的割点)，有多少条圆点到圆点的路径经过它。当这个割点被封锁后，这些路径就无法访问了

把圆点的权值看作$1$，方点权值看作$0$，然后维护子树权值和就可以求出答案

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

template<typename T>
inline void read(T &num) {
	T x = 0, f = 1; char ch = getchar();
	for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
	for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0');
	num = x * f;
}

int n, nn, m;
int head[100005], pre[1000005], to[1000005], sz;
int siz[200005];
ll ans[100005];

void addedge(int u, int v) {
	pre[++sz] = head[u]; head[u] = sz; to[sz] = v; 
	pre[++sz] = head[v]; head[v] = sz; to[sz] = u;
}

int dfn[100005], low[100005], tme, q[100005], top;
bool gd[100005];
vector<int> e[200005];

void tarjan(int x) {
	dfn[x] = low[x] = ++tme;
	q[++top] = x;
	int now = 0;
	for (int i = head[x]; i; i = pre[i]) {
		int y = to[i];
		if (!dfn[y]) {
			tarjan(y);
			low[x] = min(low[x], low[y]);
			if (dfn[x] <= low[y]) {
				n++;
				int z = 0;
				do {
					z = q[top];
					e[n].push_back(z);
					e[z].push_back(n);
					top--;
				} while (z != y);
				e[n].push_back(x);
				e[x].push_back(n);
			}
		} else {
			low[x] = min(low[x], dfn[y]);
		}
	}
}

void dfs(int x, int fa) {
	if (x <= nn) siz[x] = 1;
	for (auto y : e[x]) {
		if (y == fa) continue;
		dfs(y, x);
		if (x <= nn) {
			ans[x] += 1ll * siz[x] * siz[y];
		} 
		siz[x] += siz[y];
	}
	if (x <= nn) {
		ans[x] += 1ll * siz[x] * (nn - siz[x]);
	}
}

int main() {
	read(n); nn = n; read(m);
	for (int i = 1; i <= m; i++) {
		int a, b;
		read(a); read(b);
		addedge(a, b);
	}
	tarjan(1);
	dfs(1, 0);
	for (int i = 1; i <= nn; i++) {
		printf("%lld\n", ans[i] * 2); //u->v和v->u都要算
	}
	return 0;
}