P4630 [APIO2018] 铁人两项 (广义圆方树)

（这个才是标准的 点双的 广义园方树的写法）
转化太妙了
把方点权值设为点双大小
其余为-1
那么我们就转化为每两个圆点之间的距离和
非常巧妙
（粉兔圆方树讲的太细了

#include 
using namespace  std;
#define  int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define pb  push_back
#define inf 1ll<<62
#define endl "\n"
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define de_bug(x) cerr << #x << "=" << x << endl
#define all(a) a.begin(),a.end()
#define IOS   std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define  fer(i,a,b)  for(int i=a;i<=b;i++)
#define  der(i,a,b)  for(int i=a;i>=b;i--)
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
int n, m , k;
int dfn[N], low[N];
stack<int>s;
int idx;
int cnt;
vi g[N];
int num ;
int vis[N];
int sz[N];
int d[N];
int ans;
vi e[N];
void tarjan (int x, int fa) {
	low[x] = dfn[x] = ++idx;
	s.push(x);
	++num;
	for(auto v : g[x]) {
		if(!dfn[v]) {
			tarjan(v, x);
			low[x] = min(low[x], low[v]);
			if(low[v] >= dfn[x]) {
				int t;
				++cnt;
				d[cnt] = 0;
				while(1) {
					t = s.top();
					s.pop();
					e[cnt].push_back(t);
					e[t].push_back(cnt);
					++d[cnt];
					if(t == v)break;
				}
				e[cnt].push_back(x);
				e[x].push_back(cnt);
				++d[cnt];
			}
		} else if(v != fa) low[x] = min(low[x], dfn[v]);
	}
}
void dfs(int u, int fa) {
	if(u <= n)sz[u] = 1;
	for(auto v : e[u]) {
		if(v == fa)continue;
		dfs(v, u);
		ans += 2ll * d[u] * sz[u] * sz[v];
		sz[u] += sz[v];
	}
	ans += 2ll * d[u] * sz[u] * (num - sz[u]);
}
void solve() {
	cin >> n >> m;
	fer(i, 1, n)d[i] = -1;
	cnt = n;
	fer(i, 1, m) {
		int a, b;
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	fer(i, 1, n) {
		if(!dfn[i]) {
			num = 0;
			tarjan(i, 0);
			s.pop();
			dfs(i, 0);
		}
	}
	cout << ans << endl;

}
signed main() {
	IOS;
	int _ = 1;
	//cin>>_;
	while( _-- )
		solve();
}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101