先扔張圖：

---

為了提前了解我們采用的方法，請先閱讀《圖論學習筆記 3》。

仙人掌圖的定義：一個連通圖，且每條邊只出現在至多一個環中。

這個圖就是仙人掌圖。

這個圖也是仙人掌圖。

而這個圖就不是仙人掌圖了。

很容易發現，仙人掌圖就是在樹上連了若干條邊（$\ge 1$ 條）。所以可以視為仙人掌圖是基環樹的擴展。

---

眾所周知，我們通過想象基環樹的深搜樹形態解決了基環樹的一些問題，所以也考慮想象仙人掌圖的深搜樹。

這里就直接給圖了：

很容易發現以下性質：

• 仙人掌圖中，每一條回邊互不相交且與環一一對應，環由回邊與祖先到子孫的鏈構成。（這個比較顯然，可以簡單理解）

• 任何一個環的 $up$ 點或者是 $dn$ 點，其子樹一定包含的是完整的環。

很容易感性理解。$up$ 的子樹一定包含所有的環點，$dn$ 的子樹一定不包含所有的環點。所以就可以證了。

• 在每一個點的子樹中，至多有一個沒有遍歷到其對應的 $up$ 點的 $dn$ 點。

考慮反證法，設我們有一個點 $x$，其子樹里面有兩個沒有遍歷到其對應的 $up$ 點的 $dn$ 點。設兩個 $up$ 點為 $up1,up2$，設兩個 $dn$ 點為 $dn1,dn2$。

很容易發現，兩個 $up$ 點一定是 $x$ 的祖先。不妨這里設 $up1$ 是 $up2$ 的祖先。

容易發現，$up1$ 到 $x$ 的一整條路徑都出現在了兩個環中，所以這樣是矛盾的，原結論得證。

---

T425915 仙人掌圖最大獨立集

首先默認已經做過基環樹版本的 騎士 那道題了。

回顧一下那道題的做法，可以發現對于一條回邊 $up\to dn$ 構成的環，我們是在原有的 沒有上司的舞會那道題 $dp$ 狀態上進行了一個升維，在記錄子樹根結點有沒有選的同時還記錄了 $dn$ 有沒有選。

考慮將這種方法擴展到仙人掌圖上面，但是我們發現一個結點的子樹里面可能有很多的 $dn$（并不是只有一個環了），而且數量是會變化的，而我們又不可能 $2^n$ 記錄所有的 $dn$ 選沒選，所以在狀態設計方面遇到了一點“困難”。

但是我們發現，上述結論 3 就是為我們量身定制的，因為其他已經被考慮過的環已經不用再考慮（這是仙人掌圖，不會出現環套環的情況），所以只需要把目光放在這個沒有走到 $up$ 的 $dn$ 點就行了。

所以就可以設計狀態了。至此思路已經成型，直接把那道題的代碼拿過來改改就行了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 50010;
int n;
vector<int> v[N];
int dp[N][4];
bool stk[N], vis[N];
int up[N];
int m;void dfs(int u, int pre) {vis[u] = stk[u] = 1;dp[u][1] = dp[u][3] = 1, dp[u][0] = dp[u][2] = 0;for (auto i : v[u])if (!vis[i]) {dfs(i, u);if (up[i] != 0 && up[i] != u)up[u] = up[i];if (u == up[i]) {dp[u][0] += max(max(dp[i][0], dp[i][1]), max(dp[i][2], dp[i][3]));dp[u][1] += dp[i][0];dp[u][2] += max(max(dp[i][0], dp[i][1]), max(dp[i][2], dp[i][3]));//很容易發現，對于一個環結束的時候，可以取 dp[2] 和 dp[0] 的增量相同，dp[3] 和 dp[1] 的增量相同dp[u][3] += dp[i][0];} else {dp[u][0] += max(dp[i][0], dp[i][1]);dp[u][1] += dp[i][0];dp[u][2] += max(dp[i][2], dp[i][3]);dp[u][3] += dp[i][2];}} else if (i != pre && stk[i])up[u] = i, dp[u][1] = dp[u][2] = -1e16;stk[u] = 0;
}signed main() {cin >> n >> m;for (int i = 1; i <= m; i++) {int x, y;cin >> x >> y;v[x].push_back(y), v[y].push_back(x);}dfs(1, 0);cout << max(dp[1][0], dp[1][1]) << endl;return 0;
}

可以發現，這份代碼和騎士那道題的那份代碼是差不多了，主要改動就是把原來的單個元素 $up$ 變成了一個數組 up[]。

最大獨立集時間復雜度

學了這么多獨立集，來總結一下各種圖的求最大獨立集的時間復雜度。

首先對于一般圖，求獨立集屬于 NP 完全問題，也就是只能暴力枚舉。

對于二分圖，設點數 $n$，邊數 $m$，則可以使用網絡流將復雜度變成 $O(m\sqrt{n})$ 的級別（網絡流還沒學過qwq）。

對于仙人掌圖，也包含了樹和基環樹，可以使用深搜樹 + dp 的方式把復雜度變成 $O(n+m)$ 的級別。

對仙人掌圖進行縮點

發現仙人掌是一堆環通過一堆邊拼在一起，兩兩之間彼此不相交。顯然會發現，這個時候若把每一個環都看作是一個點，那么最終就會變成一棵樹，在上面可以跑各種各樣的科技。

那么怎么看作是一個點呢？？？通過 P5236 的圓方樹做法，我們想到了可以配合點雙連通分量進行縮點。

考慮仙人掌圖中的每一個點雙，不難發現是這樣子的：

• 每一個點雙恰好是一個簡單環，或者是恰為一條非環邊。

顯然簡單環一定是極大的點雙連通分量，但是剩下的邊中的每一條邊也會變成一個點雙連通分量，所以上面的那句話是正確的。

例如這個仙人掌圖的深搜樹，樹邊用實線，回邊用虛線：

所有的點雙連通分量現在已經用彩色線圈出來了，在旁邊寫上了新的編號。

最終得到的園方樹如下：

以前我們就知道圓方樹有著求必經點和可經點的作用，但是在對仙人掌圖縮點的時候它會有更大的作用。

觀察綠色點雙連通分量，發現其 $up$ 結點為 $3$ 號結點（這里 $up$ 結點為點雙連通分量最高的結點，而 $dn$ 結點為點雙連通分量最低的結點），而對應到圓方樹里面，發現 $3$ 就是其父親！

整理一下可得：

新性質：圓方樹里方點的父親恰好是深搜樹中其對應的點雙里最高的點。

---

考慮另一件事情：如何處理環上兩點之間的最短距離。

不妨在圓方樹里面，針對 $14$ 號方點進行舉例，即原深搜樹中的綠色點雙連通分量的部分。后面的抽象文字如果有不懂的可以對照著圖片想想為什么。

因為獲取距離的方法較為套路，這里就簡要講講思考在這個方法的過程。

發現一個環一定是一條鏈加上一條回邊，這是不由分說地。而且還可以發現兩點之間的距離要么是在這條構成環的鏈上的距離（也就是直接從深度小的點通過走鏈走到深度大的點），要么是從另一個方向過來的距離（也就是先從深度小的點走到 $up$，然后再走 $dn$，再有 $dn$ 走到深度較大的點）

顯然兩點之間的最短距離就是上面兩片粗體字得到答案的 $\min$ 值。但是這兩個答案太難算了，有沒有一些突破口呢？

顯然是有的，因為我們可以發現第一托路徑的答案 $+$ 第二托路徑的答案 $=$ 整個環的路徑權值和。

那么就可以通過路徑權值和來快速通過前者得到后者。而且路徑權值和是一個定值，因為其他地方沒地方放了，就直接把環里面的路徑權值和作為這個環對應的方點的點權即可。

而對于前面提到的第一托可能的路徑，可以使用在鏈上 $up$ 到這個點的距離來記錄。這樣就做完了。最終還有每一個方點到其 $up$ 的距離設為 $0$。

總結一下：

• 方點到其 $up$ 的邊權設為 $0$。

• 圓點到方點的邊權，設為在深搜樹中方點的 $up$ 到圓點的鏈上距離。

• 將方點的點權設為環內所有邊權的總和。