[题解]-CF1454E

Posted on In

题意

给出一棵基环树, 求树上简单路径条数

\(3 \leq n \leq 2 \cdot 10^5\)

题解

将基环树看作一个环, 环上连接着一些树, 设第\(i\)棵树有\(cnt_i\)个节点.

路径分为两种情况:

  1. 在树内. 有\(\frac{cnt_i \cdot (cnt_i - 1)}{2}\)条
  2. 由树内到树外, 有\(cnt_i \cdot (n - cnt_i)\)条(这里只计算了一半, 但当计算完全部子树后答案是完整的)

通过一遍\(DFS\)求出环, 再通过一次\(DFS\)求出每个子树大小, 答案为 \[ \sum_{i \in subtree}\frac{cnt_i\cdot(cnt_i-1)}{2} + cnt_{i}\cdot(n - cnt_i) \] 复杂度\(O(n)\)

代码

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
//E
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
const int maxn = 2e5+10;
const int maxm = maxn*2;
int head[maxn],pa[maxn];
bool loop[maxn],vis[maxn];
struct Edge{
	int f,t,next;
	Edge(int f = 0,int t = 0,int next = 0):f(f),t(t),next(next){}	
}edge[maxm];
int tcnt,cnt;
void addedge(int f,int t){
	edge[cnt] = Edge(f,t,head[f]);
	head[f] = cnt++;
}
bool ok = 0;
void pre(int u,int fa){
	if(ok)return;
	vis[u] = 1;
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].t;
		if(v == fa or ok)continue;
		if(vis[v]){
			while(u != v){
				loop[u] = 1;
				u = pa[u];
				ok = 1;
			}
			loop[v] = 1;
			return;
		}
		pa[v] = u;
		pre(v,u);
	}
}
void DFS(int u,int fa){
	tcnt++;
	for(int i = head[u];~i;i = edge[i].next){
		int v = edge[i].t;
		if(v == fa or loop[v])continue;
		DFS(v,u);
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--){
		int n;
		cin >> n;
		tcnt = 0;
		ok = 0;
		cnt = 0;
		vector<ll>res;
		for(int i = 0;i <= n;i++)head[i] = -1,loop[i] = 0,pa[i] = vis[i] = 0;
		for(int i = 1;i <= n;i++){
			int f,t;
			cin >> f >> t;
			addedge(f,t);
			addedge(t,f);
		}
		pre(1,-1);
		for(int i = 1;i <= n;i++){
			if(loop[i]){
				tcnt = 0;
				DFS(i,-1);
				res.push_back(tcnt);
			}
		}
		ll ans = 0;
		for(ll x:res)ans += x*(x-1)/2 + x*(n-x);
		cout << ans << endl;
	}
	return 0;
}