基環(huán)樹其實并不是樹，是指有n個點n條邊的圖，我們知道n個點n-1條邊的連通圖是樹，再加一條邊就會形成一個環(huán)，所以基環(huán)樹中一定有一個環(huán)，長下面這樣：

由基環(huán)樹可以引申出基環(huán)內向樹和基環(huán)外向樹

基環(huán)內向樹如下，特點是每個點的出度為1

基環(huán)外向樹如下，特點是每個點的入度為1

下面放點題，做到相關題目隨時更新

基環(huán)樹+組合數學

CF 1454E Number of Simple Paths

先記錄環(huán)上的點，每個環(huán)上的點引出去的子樹中，兩點之間都只有一條路徑，然后子樹和其他點之間都有兩條路徑（因為有個環(huán)），可以循環(huán)計算每個子樹，答案累加即可

#include <bits/stdc++.h>using namespace std;typedef pair<int, int> PII;#define int long longvoid solve()
{int n;cin >> n;vector<vector<int>> g(n + 1);vector<int> in(n + 1);for (int i = 0 ;i < n; i ++ ){int a, b;cin >> a >> b;g[a].push_back(b);g[b].push_back(a);in[a] ++ , in[b] ++ ;}queue<int> q;for (int i = 1; i <= n; i ++ ) {if (in[i] == 1) q.push(i);}while (q.size()){auto t = q.front();q.pop();for (int i = 0; i < g[t].size(); i ++ ){int j = g[t][i];in[j] -- ;if (in[j] == 1) q.push(j);}}vector<int> huan;vector<int> st(n + 1);for (int i = 1; i <= n; i ++ ){if (in[i] > 1){huan.push_back(i);st[i] = true;}}int ans = 0, sumtmp, sum = 0;vector<bool> visited(n + 1);function<void(int, int)> dfs = [&](int u, int fa){sumtmp ++ ;if (visited[u]) return;visited[u] = true;for (int i = 0; i < g[u].size(); i ++ ){int j = g[u][i];if (j == fa || visited[j] || st[j]) continue;dfs(j, u);}return;};for (auto i : huan){sumtmp = 0;dfs(i, -1);ans += sumtmp * (sumtmp - 1) / 2;ans += (sumtmp - 1) * (n - sumtmp - sum) * 2;sum += sumtmp - 1;}ans += huan.size() * (huan.size() - 1);cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t -- ){solve();}
}

基環(huán)內向樹+dfs

?？?寒假集訓1K 牛鎮(zhèn)公務員考試

基環(huán)內向樹（準確的說應該是森林）

編號 i 向 a[i] 連邊，表示對其限制，我們可以發(fā)現環(huán)之外的鏈對答案沒什么影響，因為確定了環(huán)上一點，可以倒推出鏈上的所有答案（原因就是約束關系），所以我們在環(huán)上任取一點，枚舉這個點的五種答案，然后遍歷一下環(huán)看這個答案是否合法

因為不保證聯通，所以需要遍歷每一個點

#include <bits/stdc++.h>using namespace std;#define int long long
using i64 = long long;typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;const int N = 1000010;
const int maxn = 1e6 + 1;
const int mod = 998244353;void solve()
{int n;cin >> n;vector<int> a(n + 1);vector<string> s(n + 1);for (int i = 1; i <= n; i ++ ) cin >> a[i] >> s[i];vector<bool> st(n + 1);int ans = 1;for (int i = 1; i <= n; i ++ ){if (st[i]) continue;int j = i;vector<int> huan;for (; !st[j]; j = a[j]){huan.push_back(j);st[j] = true;}auto iter = find(huan.begin(), huan.end(), j);if (iter == huan.end()) continue;huan = {iter, huan.end()};int tmp = 0;for (int k = 0; k < 5; k ++ ){int h = k;for (auto t : huan) h = (int)(s[t][h] - 'A');tmp += h == k;}ans = ans * tmp % mod;}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int t = 1;// cin >> t;while (t -- ){solve();}
}