Rockdu's Blog

地址：https://loj.ac/problem/2587

先来说说我和这道题的故事吧。

作为APIO2018最良心得分题，放在T3的位置是真的阴……

当打完了T1,T2的暴力后，才发现T3貌似很好拿分，想的是把T1，T2的二档暴力打完后来慢慢拿T3的分。于是就被坑进T1了。

T3最后只打了有环和链的、n<=10的。树的档都没看到，血亏。

知道了点双树(圆方树)后，这道题就很送分了。对于圆点统计从不同子树中选出两个点的方案，对于方点统计从不同子树选出三个点的方案，加起来就行了。

细节比较多，详见注释

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<stack>
#include<map>
#define LL long long
using namespace std;
const int maxm = 4e5 + 5;
const int maxn = 2e5 + 5;
typedef pair<int, int > pii;
map<pii, int > mp;
struct edge {
	int v, next;
} e[maxm << 2];
int head[maxn], cnt;
int n, m, u, v;
void adde(const int &u, const int &v) {
	e[cnt] = (edge) {v, head[u]};
	head[u] = cnt++;
}

stack<int > stk;
int dfn[maxn], low[maxn], vis[maxm], E_blk[maxm], bcnt, dcnt;
int ndcnt, is_sq[maxn];
int tarjan(int u) {
	dfn[u] = low[u] = ++dcnt;
	for(register int i = head[u]; ~i; i = e[i].next) {
		int v = e[i].v;
		if(vis[i >> 1]) continue;
		//点双树标记边 ，压边的栈 
		vis[i >> 1] = 1, stk.push(i);
		if(dfn[v]) {
			//点双的low不具有传递性，因为下面的子树会被点u挡住，只能用dfn[v] 
			low[u] = min(dfn[v], low[u]);
			continue;
		}
		low[u] = min(low[u], tarjan(v));
		if(low[v] >= dfn[u]) {
			int id = stk.top(); 
			//特判不在点双中的边 
			if(e[id ^ 1].v == u) {
				stk.pop();
				continue;
			}
			//在点双中才分配标号 
			++bcnt;
			do {
				id = stk.top(), stk.pop();
				E_blk[id >> 1] = bcnt;
			} while(e[id ^ 1].v != u);
		}
	}
	return low[u];
}

namespace CST {
	int head[maxn << 1], siz[maxn << 1];
	void adde(const int &u, const int &v) {
		//cerr << u << "---->" << v << endl;
		e[cnt] = (edge) {v, head[u]};
		head[u] = cnt++;
	}
	int dfs(int u, int p) {
		siz[u] = u <= n;
		for(register int i = head[u]; ~i; i = e[i].next) {
			int v = e[i].v;
			if(v == p) continue;
			siz[u] += dfs(v, u);
		}
		return siz[u];
	}
	LL GetAns(int u, int tot, int p) {
		LL ans = 0, sum = 0, tms = 0;
		//下面就是简单的讨论一下 
		siz[u] = u <= n;
		for(register int i = head[u]; ~i; i = e[i].next) {
			int v = e[i].v;
			if(v == p) continue;
			ans += GetAns(v, tot, u);
			siz[u] += siz[v];
			tms += 1ll * sum * siz[v], sum += siz[v];
		}
		tms += (tot - siz[u]) * sum;
		sum += tot - siz[u];
		tms *= 2;
		if(u <= n) {
			ans += tms;
		} else {
			//ans += tms;
			for(register int i = head[u]; ~i; i = e[i].next) {
				int v = e[i].v;
				if(v == p) continue;
				ans += 1ll * (tms - 2 * siz[v] * (sum - siz[v]));
			}
			ans += 1ll * (tms - 2 * (tot - siz[u]) * (sum - (tot - siz[u])));
		}
		//printf("%d %d\n", u, ans);
		return ans;
	}
}

int main() {
	memset(head, -1, sizeof(head));
	memset(CST::head, -1, sizeof(CST::head));
	scanf("%d%d", &n, &m);
	for(register int i = 1; i <= m; ++i)
		scanf("%d%d", &u, &v), adde(u, v), adde(v, u);
	for(register int i = 1; i <= n; ++i)
		if(!dfn[i]) tarjan(i);
	for(register int i = 0; i < m; ++i) {
		u = e[i << 1].v, v = e[i << 1 | 1].v;
		if(!E_blk[i]) {
			if(u > v) swap(u, v);
			if(mp[make_pair(u, v)]) continue;
			CST::adde(u, v), CST::adde(v, u);
			mp[make_pair(u, v)] = 1;
		} else {
			int S = E_blk[i] + n;
			if(!mp[make_pair(u, S)]) {
				CST::adde(u, S), CST::adde(S, u);
				mp[make_pair(u, S)] = 1;
			}
			if(!mp[make_pair(v, S)]) {
				CST::adde(v, S), CST::adde(S, v);
				mp[make_pair(v, S)] = 1;
			}
		}
	}
	LL ans = 0;
	for(register int i = 1; i <= n; ++i)
		if(!CST::siz[i]) {
			CST::dfs(i, 0);
			ans += CST::GetAns(i, CST::siz[i], 0);
		}
	printf("%lld\n", ans);
	return 0;
}