圓方樹

引入

我們注意到，樹結構相比普通圖具有諸多優良特性。若能將在無向圖上求解的問題轉化為樹結構問題，往往能大幅簡化求解過程。圓方樹正是實現這一轉化的有效工具。

定義

我們稱原圖中的點為"圓點"。通過引入方點并調整邊的關系，可以構造出一棵樹。通過合理賦權，使這棵樹能夠保持原圖的某些特性，從而將原問題轉化為樹上的問題。具體構建過程如下：對于每個點雙連通分量，首先刪除其中所有圓點之間的直接連接邊。然后為該點雙新增一個方點，并將該點雙內的所有圓點都與這個方點相連。這樣構建出的圖是一個無環的連通圖，即所謂的圓方樹。構建過程本身并不復雜，只要掌握點雙連通分量的求法即可完成。而難點在于：如何恰當設置權值，使得在圓方樹上能夠求解原問題。

代碼

void tarjan(int u, int fa) {low[u] = dfn[u] = ++tot;sta.push(u);for (auto v : ve[u]) {if (v == fa) continue;if (!dfn[v]) {tarjan(v, u);low[u] = min(low[u], low[v]);if (low[v] >= dfn[u]) {      // 發現點雙int now = 0;sid++;    // 方點id，初始值為nvn[u].push_back(sid);    //建雙向邊vn[sid].push_back(u);while (now != v) {now = sta.top();vn[now].push_back(sid);    //建雙向邊vn[sid].push_back(now);sta.pop();}}} else {low[u] = min(low[u], dfn[v]);}}
}

例題

鐵人兩項
給定一張無向圖，問有多少互不相同三元組<$a$, $b$, $c$>
使得存在一條從 $a$ 到 $b$ 經過 $c$ 的簡單路徑。

題解

在同一個點雙連通分量中，任意兩點之間的所有簡單路徑的并集恰好構成該點雙。對于任意兩點，其簡單路徑所經過的點集可表示為路徑上各點雙的并集。在圓方樹模型中，該點集對應為： 兩個圓點路徑上的所有圓點和路徑上方點相鄰的所有圓點 。由于限制條件 $c\ne a$ 且 $c\ne b$，最終答案為該點集大小減 2。 具體實現時，考慮圓方樹上的權值設計： 將方點權值設為相鄰圓點數量，并將圓點權值設為 -1（避免相鄰方點重復計算），而路徑端點不計入貢獻。這樣，圓方樹上兩圓點間路徑的點權和即為所求答案。問題轉化為統計樹上所有圓點對的路徑權值和，可通過樹形 DP 計算每個點的貢獻（點權 $\times$ 經過該點的路徑數）來高效求解。