圓方樹

在閲讀下列內容之前，請務必瞭解 圖論相關概念 部分。

相關閲讀：割點和橋。

引入

眾所周知，樹（或森林）有很好的性質，並且容易通過很多常見數據結構維護。

而一般圖則沒有那麼好的性質，所幸有時我們可以把一般圖上的某些問題轉化到樹上考慮。

而圓方樹（Block forest 或 Round-square tree）¹就是一種將圖變成樹的方法。本文將介紹圓方樹的構建，性質和一些應用。

限於篇幅，本文中有一些結論未經證明，讀者可以自行理解或證明。

定義

圓方樹最初是處理「仙人掌圖」（每條邊在不超過一個簡單環中的無向圖）的一種工具，不過發掘它的更多性質，有時我們可以在一般無向圖上使用它。

要介紹圓方樹，首先要介紹 點雙連通分量。

一個 點雙連通圖 的一個定義是：圖中任意兩不同點之間都有至少兩條點不重複的路徑。
點不重複既指路徑上點不重複（簡單路徑），也指兩條路徑的交集為空（當然，路徑必然都經過出發點和到達點，這不在考慮範圍內）。

可以發現對於只有一個點的圖比較難定義它是不是一個點雙，這裏先不考慮節點數為 \(1\) 的圖。

一個近乎等價的定義是：不存在割點的圖。
這個定義只在圖中只有兩個點，一條連接它們的邊時失效。它沒有割點，但是並不能找到兩條不相交的路徑，因為只有一條路徑。
（也可以理解為那一條路徑可以算兩次，的確沒有交，因為不經過其他點）

雖然原始的定義的確是前者，但是為了方便，我們規定點雙圖的定義採用後者。

而一個圖的 點雙連通分量 則是一個 極大點雙連通子圖。
與強連通分量等不同，一個點可能屬於多個點雙，但是一條邊屬於恰好一個點雙（如果定義採用前者則有可能不屬於任何點雙）。

在圓方樹中，原來的每個點對應一個 圓點，每一個點雙對應一個 方點。
所以共有 \(n+c\) 個點，其中 \(n\) 是原圖點數，\(c\) 是原圖點雙連通分量的個數。

而對於每一個點雙連通分量，它對應的方點向這個點雙連通分量中的每個點連邊。
每個點雙形成一個「菊花圖」，多個「菊花圖」通過原圖中的割點連接在一起（因為點雙的分隔點是割點）。

顯然，圓方樹中每條邊連接一個圓點和一個方點。

下面的圖顯示了一張圖對應的點雙和圓方樹形態。²

圓方樹的點數小於 \(2n\)，這是因為割點的數量小於 \(n\)，所以請注意各種數組大小要開兩倍。

其實，如果原圖連通，則「圓方樹」才是一棵樹，如果原圖有 \(k\) 個連通分量，則它的圓方樹也會形成 \(k\) 棵樹形成的森林。

如果原圖中某個連通分量只有一個點，則需要具體情況具體分析，我們在後續討論中不考慮孤立點。

過程

對於一個圖，如何構造出它的圓方樹呢？首先可以發現如果圖不連通，可以拆分成每個連通子圖考慮，所以我們只考慮連通圖。

因為圓方樹是基於點雙連通分量的，而點雙連通分量又基於割點，所以只需要用類似求割點的方法即可。

求割點的常用算法是 Tarjan 算法，如果你會了理解下面的內容就很簡單了，如果你不會也沒關係。

我們跳過 Tarjan 求割點，直接介紹圓方樹使用的算法（其實是 Tarjan 的變體）：

對圖進行 DFS，並且中間用到了兩個關鍵數組 dfn 和 low（類似於 Tarjan）。

dfn[u] 存儲的是節點 \(u\) 的 DFS 序，即第一次訪問到 \(u\) 時它是第幾個被訪問的節點。
low[u] 存儲的是節點 \(u\) 的 DFS 樹中的子樹中的某個點 \(v\) 通過 最多一次返祖邊或向父親的樹邊 能訪問到的點的 最小 DFS 序。
如果沒有聽説過 Tarjan 算法可能會有點難理解，讓我們舉個例子吧：

（可以發現這張圖其實和上面圖片中的圖等價）
這裏樹邊從上至下用直線畫出，返祖邊從下至上用曲線畫出。節點的編號便是它的 DFS 序。

則有 low 數組如下：

\(i\)	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\)	\(8\)	\(9\)
\(\mathrm{low}[i]\)	\(1\)	\(1\)	\(1\)	\(3\)	\(3\)	\(4\)	\(3\)	\(3\)	\(7\)

並不是很難理解吧，注意這裏 \(9\) 的 low 是 \(7\)，與一些求割點的做法有差異，因為為了方便，我們規定了可以通過父邊向上，但主要思想是相同的。

我們可以很容易地寫出計算 dfn 和 low 的 DFS 函數（初始時 dfn 數組清零）：

實現

C++Python

void Tarjan(int u) {
  low[u] = dfn[u] = ++dfc;                // low 初始化為當前節點 dfn
  for (int v : G[u]) {                    // 遍歷 u 的相鄰節點
    if (!dfn[v]) {                        // 如果未訪問過
      Tarjan(v);                          // 遞歸
      low[u] = std::min(low[u], low[v]);  // 未訪問的和 low 取 min
    } else
      low[u] = std::min(low[u], dfn[v]);  // 已訪問的和 dfn 取 min
  }
}

def Tarjan(u):
    low[u] = dfn[u] = dfc # low 初始化為當前節點 dfn
    dfc = dfc + 1
    for v in G[u]: # 遍歷 u 的相鄰節點
        if dfn[v] == False: # 如果未訪問過
            Tarjan(v) # 遞歸
            low[u] = min(low[u], low[v]) # 未訪問的和 low 取 min
        else:
            low[u] = min(low[u], dfn[v]) # 已訪問的和 dfn 取 min

接下來，我們考慮點雙和 DFS 樹以及這兩個數組之間的關聯。

可以發現，每個點雙在 DFS 樹上是一棵連通子樹，並至少包含兩個點；特別地，最頂端節點僅往下接一個點。

同時還可以發現每條樹邊恰好在一個點雙內。

我們考慮一個點雙在 DFS 樹中的最頂端節點 \(u\)，在 \(u\) 處確定這個點雙，因為 \(u\) 的子樹包含了整個點雙的信息。

因為至少有兩個點，考慮這個點雙的下一個點 \(v\)，則有 \(u\)，\(v\) 之間存在一條樹邊。

不難發現，此時一定有 \(\mathrm{low}[v]=\mathrm{dfn}[u]\)。
更準確地説，對於一條樹邊 \(u\to v\)，\(u,v\) 在同一個點雙中，且 \(u\) 是這個點雙中深度最淺的節點 當且僅當 \(\mathrm{low}[v]=\mathrm{dfn}[u]\)。

那麼我們可以在 DFS 的過程中確定哪些地方存在點雙，但是還不能準確確定一個點雙所包含的點集。

這並不難處理，我們可以在 DFS 過程中維護一個棧，存儲還未確定所屬點雙（可能有多個）的節點。

在找到點雙時，點雙中除了 \(u\) 以外的其他的點都集中在棧頂端，只需要不斷彈棧直到彈出 \(v\) 為止即可。

當然，我們可以同時處理被彈出的節點，只要將其和新建的方點連邊即可。最後還要讓 \(u\) 和方點連邊。

這樣就很自然地完成了圓方樹的構建，我們可以給方點標號為 \(n+1\) 開始的整數，這樣可以有效區分圓點和方點。

這部分可能講述得不夠清晰，下面貼出一份代碼，附有詳盡註釋以及幫助理解的輸出語句和一份樣例，建議讀者複製代碼並自行實踐理解，畢竟代碼才是最能幫助理解的（不要忘記開 c++11）。

實現

#include <algorithm>
#include <cstdio>
#include <vector>

const int MN = 100005;

int N, M, cnt;
std::vector<int> G[MN], T[MN * 2];

int dfn[MN], low[MN], dfc;
int stk[MN], tp;

void Tarjan(int u) {
  printf("  Enter : #%d\n", u);
  low[u] = dfn[u] = ++dfc;                // low 初始化為當前節點 dfn
  stk[++tp] = u;                          // 加入棧中
  for (int v : G[u]) {                    // 遍歷 u 的相鄰節點
    if (!dfn[v]) {                        // 如果未訪問過
      Tarjan(v);                          // 遞歸
      low[u] = std::min(low[u], low[v]);  // 未訪問的和 low 取 min
      if (low[v] == dfn[u]) {  // 標誌着找到一個以 u 為根的點雙連通分量
        ++cnt;                 // 增加方點個數
        printf("  Found a New BCC #%d.\n", cnt - N);
        // 將點雙中除了 u 的點退棧，並在圓方樹中連邊
        for (int x = 0; x != v; --tp) {
          x = stk[tp];
          T[cnt].push_back(x);
          T[x].push_back(cnt);
          printf("    BCC #%d has vertex #%d\n", cnt - N, x);
        }
        // 注意 u 自身也要連邊（但不退棧）
        T[cnt].push_back(u);
        T[u].push_back(cnt);
        printf("    BCC #%d has vertex #%d\n", cnt - N, u);
      }
    } else
      low[u] = std::min(low[u], dfn[v]);  // 已訪問的和 dfn 取 min
  }
  printf("  Exit : #%d : low = %d\n", u, low[u]);
  printf("  Stack:\n    ");
  for (int i = 1; i <= tp; ++i) printf("%d, ", stk[i]);
  puts("");
}

int main() {
  scanf("%d%d", &N, &M);
  cnt = N;  // 點雙 / 方點標號從 N 開始
  for (int i = 1; i <= M; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    G[u].push_back(v);  // 加雙向邊
    G[v].push_back(u);
  }
  // 處理非連通圖
  for (int u = 1; u <= N; ++u)
    if (!dfn[u]) Tarjan(u), --tp;
  // 注意到退出 Tarjan 時棧中還有一個元素即根，將其退棧
  return 0;
}

提供一個測試用例：

13 15
1 2
2 3
1 3
3 4
3 5
4 5
5 6
4 6
3 7
3 8
7 8
7 9
10 11
11 10
11 12

這個例子對應的圖（包含了重邊和孤立點的情況）：

例題

我們講一些可以使用圓方樹求解的例題。

「APIO2018」鐵人兩項

題意簡述

給定一張簡單無向圖，問有多少對三元組 \(\langle s, c, f \rangle\)（\(s, c, f\) 互不相同）使得存在一條簡單路徑從 \(s\) 出發，經過 \(c\) 到達 \(f\)。

題解

説到簡單路徑，就必須提一個關於點雙很好的性質：對於一個點雙中的兩點，它們之間簡單路徑的並集，恰好完全等於這個點雙。
即同一個點雙中的兩不同點 \(u,v\) 之間一定存在一條簡單路徑經過給定的在同一個點雙內的另一點 \(w\)。

這個性質的證明：

• 顯然如果簡單路徑出了點雙，就不可能再回到這個點雙中，否則會和點雙的定義衝突。
• 所以我們只需考慮證明一個點雙連通圖中任意三不同點 \(u,v,c\)，必存在一條從 \(u\) 到 \(v\) 的簡單路徑經過 \(c\)。
• 首先排除點數為 \(2\) 的情況，它滿足這個性質，但是無法取出 \(3\) 個不同點。
• 對於餘下的情況，考慮建立網絡流模型，源點向 \(c\) 連容量為 \(2\) 的邊，\(u\) 和 \(v\) 向匯點連容量為 \(1\) 的邊。
• 原圖中的雙向邊 \(\langle x,y\rangle\)，變成 \(x\) 向 \(y\) 連一條容量為 \(1\) 的邊，\(y\) 也向 \(x\) 連一條容量為 \(1\) 的邊。
• 最後，給除了源點，匯點和 \(c\) 之外的每個點賦上 \(1\) 的容量，這可以通過拆點實現。
• 因為源點到 \(c\) 的邊的容量為 \(2\)，那麼如果這個網絡最大流為 \(2\)，則證明一定有路徑經過 \(c\)。
• 考慮最大流最小割定理，顯然最小割小於等於 \(2\)，接下來只要證最小割大於 \(1\)。
• 這等價於證明割掉任意一條容量為 \(1\) 的邊，是無法使源點和匯點不連通的。
• 考慮割掉 \(u\) 或 \(v\) 與匯點連接的點，根據點雙的第一種定義，必然存在簡單路徑從 \(c\) 到另一個沒割掉的點。
• 考慮割掉一個節點拆點形成的邊，這等價於刪除一個點，根據點雙的第二種定義，餘下的圖仍然連通。
• 考慮割掉一條由原先的邊建出的邊，這等價於刪除一條邊，這比刪除一個點更弱，顯然存在路徑。
• 所以我們證明了最小割大於 \(1\)，即最大流等於 \(2\)。證畢。

這個結論能告訴我們什麼呢？它告訴了我們：考慮兩圓點在圓方樹上的路徑，與路徑上經過的方點相鄰的圓點的集合，就等於原圖中兩點簡單路徑上的點集。

回到題目，考慮固定 \(s\) 和 \(f\)，求合法的 \(c\) 的數量，顯然有合法 \(c\) 的數量等於 \(s,f\) 之間簡單路徑的並集的點數減 \(2\)（去掉 \(s,f\) 本身）。

那麼，對原圖建出圓方樹後，兩點之間簡單路徑的點數，就和它們在圓方樹上路徑經過的方點（點雙）和圓點的個數有關。

接下來是圓方樹的一個常用技巧：路徑統計時，點賦上合適的權值。
本題中，每個方點的權值為對應點雙的大小，而每個圓點權值為 \(-1\)。

這樣賦權後則有兩圓點間圓方樹上路徑點權和，恰好等於原圖中簡單路徑並集大小減 \(2\)。

問題轉化為統計圓方樹上 \(\sum\) 兩圓點路徑權值和。

換個角度考慮，改為統計每一個點對答案的貢獻，即權值乘以經過它的路徑條數，這可以通過簡單的樹形 DP 求出。

最後，不要忘記處理圖不連通的情況。下面是對應代碼：

參考代碼

#include <algorithm>
#include <cstdio>
#include <vector>

const int MN = 100005;

int N, M, cnt;
std::vector<int> G[MN], T[MN * 2];
long long Ans;

int dfn[MN], low[MN], dfc, num;
int stk[MN], tp;

int wgh[MN * 2];

void Tarjan(int u) {  // 求点双
  low[u] = dfn[u] = ++dfc;
  stk[++tp] = u;
  ++num;
  for (int v : G[u]) {
    if (!dfn[v]) {
      Tarjan(v);
      low[u] = std::min(low[u], low[v]);
      if (low[v] == dfn[u]) {
        wgh[++cnt] = 0;
        for (int x = 0; x != v; --tp) {
          x = stk[tp];
          T[cnt].push_back(x);
          T[x].push_back(cnt);
          ++wgh[cnt];
        }
        T[cnt].push_back(u);
        T[u].push_back(cnt);
        ++wgh[cnt];
      }
    } else
      low[u] = std::min(low[u], dfn[v]);
  }
}

int vis[MN * 2], siz[MN * 2];

void DFS(int u, int fz) {  // dfs求值
  vis[u] = 1;
  siz[u] = (u <= N);
  for (int v : T[u])
    if (v != fz) {
      DFS(v, u);
      Ans += 2ll * wgh[u] * siz[u] * siz[v];
      siz[u] += siz[v];
    }
  Ans += 2ll * wgh[u] * siz[u] * (num - siz[u]);
}

int main() {
  scanf("%d%d", &N, &M);
  for (int u = 1; u <= N; ++u) wgh[u] = -1;
  cnt = N;
  for (int i = 1; i <= M; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  for (int u = 1; u <= N; ++u)
    if (!dfn[u]) {
      num = 0;
      Tarjan(u), --tp;
      DFS(u, 0);
    }
  printf("%lld\n", Ans);
  return 0;
}

順帶一提，剛剛的測試用例在這題的答案是 \(212\)。

Codeforces #487 E. Tourists

題意簡述

給定一張簡單無向連通圖，要求支持兩種操作：

1. 修改一個點的點權。
2. 詢問兩點之間所有簡單路徑上點權的最小值。

題解

同樣地，我們建出原圖的圓方樹，令方點權值為相鄰圓點權值的最小值，問題轉化為求路徑上最小值。

路徑最小值可以使用樹鏈剖分和線段樹維護，但是修改呢？

一次修改一個圓點的點權，需要修改所有和它相鄰的方點，這樣很容易被卡到 \(\mathcal{O}(n)\) 個修改。

這時我們利用圓方樹是棵樹的性質，令方點權值為自己的兒子圓點的權值最小值，這樣的話修改時只需要修改父親方點。

對於方點的維護，只需要對每個方點開一個 multiset 維護權值集合即可。

需要注意的是查詢時若 LCA 是方點，則還需要查 LCA 的父親圓點的權值。

注意：圓方樹點數要開原圖的兩倍，否則會數組越界。

參考代碼

#include <algorithm>
#include <cstdio>
#include <set>
#include <vector>

const int MN = 100005;
const int MS = 524288;
const int Inf = 0x7fffffff;

int N, M, Q, cnt;
int w[MN * 2];
std::vector<int> G[MN], T[MN * 2];
std::multiset<int> S[MN * 2];

int dfn[MN * 2], low[MN], dfc;
int stk[MN], tp;

void Tarjan(int u) {
  low[u] = dfn[u] = ++dfc;
  stk[++tp] = u;
  for (int v : G[u]) {
    if (!dfn[v]) {
      Tarjan(v);
      low[u] = std::min(low[u], low[v]);
      if (low[v] == dfn[u]) {
        ++cnt;
        for (int x = 0; x != v; --tp) {
          x = stk[tp];
          T[cnt].push_back(x);
          T[x].push_back(cnt);
        }
        T[cnt].push_back(u);
        T[u].push_back(cnt);
      }
    } else
      low[u] = std::min(low[u], dfn[v]);
  }
}

int idf[MN * 2], faz[MN * 2], siz[MN * 2], dep[MN * 2], son[MN * 2],
    top[MN * 2];

void DFS0(int u, int fz) {
  faz[u] = fz, dep[u] = dep[fz] + 1, siz[u] = 1;
  for (int v : T[u])
    if (v != fz) {
      DFS0(v, u);
      siz[u] += siz[v];
      if (siz[son[u]] < siz[v]) son[u] = v;
    }
}

void DFS1(int u, int fz, int tp) {
  dfn[u] = ++dfc, idf[dfc] = u, top[u] = tp;
  if (son[u]) DFS1(son[u], u, tp);
  for (int v : T[u])
    if (v != fz && v != son[u]) DFS1(v, u, v);
}

#define li (i << 1)
#define ri (i << 1 | 1)
#define mid ((l + r) >> 1)
#define ls li, l, mid
#define rs ri, mid + 1, r

int dat[MS];

void Build(int i, int l, int r) {  // 建树
  if (l == r) {
    dat[i] = w[idf[l]];
    return;
  }
  Build(ls), Build(rs);
  dat[i] = std::min(dat[li], dat[ri]);
}

void Mdf(int i, int l, int r, int p, int x) {  // 获取最小值
  if (l == r) {
    dat[i] = x;
    return;
  }
  if (p <= mid)
    Mdf(ls, p, x);
  else
    Mdf(rs, p, x);
  dat[i] = std::min(dat[li], dat[ri]);
}

int Qur(int i, int l, int r, int a, int b) {  // 查询
  if (r < a || b < l) return Inf;
  if (a <= l && r <= b) return dat[i];
  return std::min(Qur(ls, a, b), Qur(rs, a, b));
}

int main() {
  scanf("%d%d%d", &N, &M, &Q);
  for (int i = 1; i <= N; ++i) scanf("%d", &w[i]);
  cnt = N;
  for (int i = 1; i <= M; ++i) {
    int u, v;
    scanf("%d%d", &u, &v);
    G[u].push_back(v);
    G[v].push_back(u);
  }
  Tarjan(1), DFS0(1, 0), dfc = 0, DFS1(1, 0, 1);
  for (int i = 1; i <= N; ++i)
    if (faz[i]) S[faz[i]].insert(w[i]);
  for (int i = N + 1; i <= cnt; ++i) w[i] = *S[i].begin();
  Build(1, 1, cnt);
  for (int q = 1; q <= Q; ++q) {
    char opt[3];
    int x, y;
    scanf("%s%d%d", opt, &x, &y);
    if (*opt == 'C') {
      Mdf(1, 1, cnt, dfn[x], y);
      if (faz[x]) {
        int u = faz[x];
        S[u].erase(S[u].lower_bound(w[x]));
        S[u].insert(y);
        if (w[u] != *S[u].begin()) {
          w[u] = *S[u].begin();
          Mdf(1, 1, cnt, dfn[u], w[u]);
        }
      }
      w[x] = y;
    } else {
      int Ans = Inf;
      while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) std::swap(x, y);
        Ans = std::min(Ans, Qur(1, 1, cnt, dfn[top[x]], dfn[x]));
        x = faz[top[x]];
      }
      if (dfn[x] > dfn[y]) std::swap(x, y);
      Ans = std::min(Ans, Qur(1, 1, cnt, dfn[x], dfn[y]));
      if (x > N) Ans = std::min(Ans, w[faz[x]]);
      printf("%d\n", Ans);
    }
  }
  return 0;
}

「SDOI2018」戰略遊戲

題意簡述

給出一個簡單無向連通圖。有 \(q\) 次詢問：

每次給出一個點集 \(S\)（\(2 \le |S| \le n\)），問有多少個點 \(u\) 滿足 \(u \notin S\) 且刪掉 \(u\) 之後 \(S\) 中的點不全在一個連通分量中。

每個測試點有多組數據。

題解

先建出圓方樹，則變為詢問 \(S\) 在圓方樹上對應的連通子圖中的圓點個數減去 \(|S|\)。

如何計算連通子圖中的圓點個數？有一個方法：

把圓點的權值放到它和它的父親方點的邊上，問題轉化為求邊權和，這個問題可以參考 「SDOI2015」尋寶遊戲 的一種解法。
即把 \(S\) 中的點按照 DFS 序排序，計算排序後相鄰兩點的距離和（還包括首尾兩點之間的距離），答案就是距離和的一半，因為每條邊只被經過兩次。

最後，如果子圖中的深度最淺的節點是圓點，答案還要加上 \(1\)，因為我們沒有統計到它。

因為有多組數據，要注意初始化數組。

參考代碼

#include <algorithm>
#include <cstdio>
#include <vector>

const int MN = 100005;

int N, M, Q, cnt;
std::vector<int> G[MN], T[MN * 2];

int dfn[MN * 2], low[MN], dfc;
int stk[MN], tp;

void Tarjan(int u) {  // 求点双，准备建树
  low[u] = dfn[u] = ++dfc;
  stk[++tp] = u;
  for (int v : G[u]) {
    if (!dfn[v]) {
      Tarjan(v);
      low[u] = std::min(low[u], low[v]);
      if (low[v] == dfn[u]) {
        ++cnt;
        for (int x = 0; x != v; --tp) {
          x = stk[tp];
          T[cnt].push_back(x);
          T[x].push_back(cnt);
        }
        T[cnt].push_back(u);
        T[u].push_back(cnt);
      }
    } else
      low[u] = std::min(low[u], dfn[v]);
  }
}

int dep[MN * 2], faz[MN * 2][18], dis[MN * 2];

void DFS(int u, int fz) {
  dfn[u] = ++dfc;
  dep[u] = dep[faz[u][0] = fz] + 1;
  dis[u] = dis[fz] + (u <= N);
  for (int j = 0; j < 17; ++j) faz[u][j + 1] = faz[faz[u][j]][j];
  for (int v : T[u])
    if (v != fz) DFS(v, u);
}

int LCA(int x, int y) {  // 最近公共祖先
  if (dep[x] < dep[y]) std::swap(x, y);
  for (int j = 0, d = dep[x] - dep[y]; d; ++j, d >>= 1)
    if (d & 1) x = faz[x][j];
  if (x == y) return x;
  for (int j = 17; ~j; --j)
    if (faz[x][j] != faz[y][j]) x = faz[x][j], y = faz[y][j];
  return faz[x][0];
}

int main() {
  int Ti;
  scanf("%d", &Ti);
  while (Ti--) {
    scanf("%d%d", &N, &M);
    for (int i = 1; i <= N; ++i) {
      G[i].clear();
      dfn[i] = low[i] = 0;
    }
    for (int i = 1; i <= N * 2; ++i) T[i].clear();
    for (int i = 1, x, y; i <= M; ++i) {
      scanf("%d%d", &x, &y);
      G[x].push_back(y);
      G[y].push_back(x);
    }
    cnt = N;
    dfc = 0, Tarjan(1), --tp;
    dfc = 0, DFS(1, 0);
    scanf("%d", &Q);
    while (Q--) {
      static int S, A[MN];
      scanf("%d", &S);
      int Ans = -2 * S;
      for (int i = 1; i <= S; ++i) scanf("%d", &A[i]);
      std::sort(A + 1, A + S + 1, [](int i, int j) { return dfn[i] < dfn[j]; });
      for (int i = 1; i <= S; ++i) {
        int u = A[i], v = A[i % S + 1];
        Ans += dis[u] + dis[v] - 2 * dis[LCA(u, v)];
      }
      if (LCA(A[1], A[S]) <= N) Ans += 2;
      printf("%d\n", Ans / 2);
    }
  }
  return 0;
}

外部鏈接

immortalCO，圓方樹——處理仙人掌的利器，Universal OJ。

參考資料與註釋

---

1. 2017 年陳俊錕同學在他的 IOI2017 中國國家集訓隊論文《〈神奇的子圖〉命題報告及其拓展》中定義並命名了圓方樹這一結構。 ↩

2. 陳俊錕，《平凡的圓方樹和神奇的（動態）動態規劃》，NOI2018 冬令營，第 4 頁。 ↩

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：GitPinkRabbit, Early0v0, Backl1ght, mcendu, ksyx, iamtwz, Xeonacid, kenlig, Menci, Enter-tainer, CCXXXI
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用