题解 洛谷P3469

题目每个割点去掉后会导致多少对点不能连通

考虑跑Tarjan的时候记录每个儿子的size，那么去掉这个割点后其他的点都不能和这个儿子连通

注意每个点去掉后它本身就不能与其他所有点连通

还有就是题目里求的是有序点对，所以应将总方案数\(×2\)

#include <algorithm>

#include <cctype>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <ctime>

#include <iostream>

#include <queue>

#include <vector>

#define il inline

#define re register

#define gc getchar

#define LL long long

#define int LL

#define D() \

// cerr << __LINE__ << endl

using namespace std;

template <typename T>

void read(T &s)

{

	s = 0;

	char ch;

	while (ch = gc(), !isdigit(ch))

		;

	while (s = s * 10 + ch - '0', ch = gc(), isdigit(ch))

		;

}

const int MAXN = 600000;

int cnt = 0;

int vis[MAXN];

int tot = 0;

int del[MAXN];

int dfn[MAXN], low[MAXN];

int sta[MAXN], top;

int ans[MAXN];

int sze[MAXN];

vector<int> edge[MAXN];

vector<int> edge2[MAXN];

il void insert(int u, int v)

{

	edge[u].push_back(v);

	edge[v].push_back(u);

}

il void insert2(int u, int v)

{

	edge2[u].push_back(v);

}

int n;

void tarjan(int u, int fa)

{

	int t = 0;

	int child = 0;

	vis[u] = 1;

	dfn[u] = low[u] = ++tot;

	sta[++top] = u;

	sze[u] = 1;

	for (auto v : edge[u])

		if (!dfn[v])

		{

			tarjan(v, u);

			sze[u] += sze[v];

			++child;

			if ((fa == -1 && child > 1) || (fa != -1 && low[v] >= dfn[u]))

			{

				ans[u] += sze[v] * t;

				t += sze[v];

			}

			low[u] = min(low[u], low[v]);

		}

		else if (vis[v])

			low[u] = min(low[u], dfn[v]);

	ans[u] += t * (n - t - 1);

	if (low[u] == dfn[u])

	{

		while (sta[top] != u)

		{

			int y = sta[top--];

			vis[y] = 0;

		}

		top--;

		vis[u] = 0;

	}

}

signed main()

{

	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	int m, a, b;

	cin >> n >> m;

	for (int i = 1; i <= m; ++i)

	{

		cin >> a >> b;

		insert(a, b);

	}

	for (int i = 1; i <= n; ++i)

		if (!dfn[i])

			tarjan(i, -1);

	for (int i = 1; i <= n; ++i)

		cout << (((n - 1 + ans[i]) << 1)) << endl;

}