1. 核心算法思想

题目要求找出一个点 $x$（$x \notin S$），使得删掉 $x$ 后，集合 $S$ 中至少有两个点不连通。 这实际上是在问：在给定的图上，有哪些点是集合 $S$ 中某两点路径上的必经点（割点）？

圆方树 (Block-Cut Tree)

由于原图是一张一般的无向图（可能包含环），直接处理路径并不容易。我们可以将原图转化为 圆方树：

• 圆点 (Round Node)：代表原图中的点（城市），编号 $1 \sim n$。
• 方点 (Square Node)：代表原图中的点双连通分量（Biconnected Component），编号 $n+1 \sim n+cnt$。
• 连边：如果原图中的点 $u$ 属于某个点双连通分量 $v$，则在圆方树中连接圆点 $u$ 和方点 $v$。

圆方树的性质：

1. 圆方树是一棵树。
2. 原图中 $u$ 到 $v$ 的所有简单路径的并集，对应圆方树上 $u$ 到 $v$ 的简单路径。
3. 关键性质：原图中 $u, v$ 之间的必经点（割点），就是圆方树上 $u$ 到 $v$ 路径上的所有 圆点。

问题转化

题目变成了：在圆方树上，求包含集合 $S$ 中所有点的最小连通子图（即 $S$ 的生成树/虚树）中，包含了多少个圆点。 最后答案要减去 $|S|$（因为题目要求 $x$ 是小 C 没占领 的城市）。

2. 代码逻辑解析

Step 1: 构建圆方树 (dfs 函数)

使用 Tarjan 算法寻找点双连通分量。

• sta 是栈，用来存储当前遍历到的节点。
• 当发现 low[v] >= num[u] 时，说明找到了一个点双连通分量。
• 创建一个新的方点 square + n。
• 将栈中的点弹出并与方点连边，直到弹出 v 为止。
• 注意：u 也是该点双的一部分，也要连边，但不能弹出 u（因为 u 可能是多个点双的割点）。

Step 2: 树上预处理 (work 函数)

在构建好的圆方树上进行 DFS：

• 计算倍增数组 par 用于求 LCA。
• 计算时间戳 tin, tout 用于判断祖先关系。
• 计算点权前缀和 dep：
  • 我们只关心 圆点 的数量。
  • 令圆点权值为 1，方点权值为 0。
  • 代码中 dep[v] = dep[u] + (v <= n) 实现了这一点：如果 v 是圆点（v <= n），深度加 1，否则不变。
  • 这样，树上两点 $u, v$ 路径上的圆点数量可以由 dep 快速计算。

Step 3: 求解询问 (process 函数中的 while(q--))

对于每次询问的集合 $S$（代码中为 terminal）：

1. 排序：按照 DFS 序（tin）对 $S$ 中的点进行排序。这是一个处理树上点集路径并集的经典技巧。
2. 计算路径并的大小：
   • 为了求 $S$ 中所有点构成的连通块包含的圆点数，我们可以利用公式：$$Ans = \frac{1}{2} \left( \sum_{i=0}^{k-1} dist(p_i, p_{i+1}) \right) + Weight(LCA(S)) $$其中 $p_k = p_0$（首尾相连），$dist(u, v)$ 是圆方树上路径的圆点数。
   • 代码中的距离计算方式是：dep[u] + dep[v] - 2 * dep[lca(u, v)]。
     • 注意：这个公式计算的是 $u$ 到 $v$ 路径上 不包含 LCA 的圆点数（如果 LCA 是圆点，它被减了两次，实际上应该只减一次）。
   • 循环计算相邻两点的距离并累加。
3. 修正：
   • 累加的结果 answer 除以 2。
   • 由于上述距离公式可能在 LCA 处处理有细微差异（主要取决于 LCA 是圆点还是方点），代码最后做了一个修正： if (lca(terminal[0], terminal.back()) <= n) answer++; 如果整个集合 $S$ 的最近公共祖先（LCA）是圆点，那么这个圆点在之前的计算中被抵消掉了（或者没算进去），需要加回来。
4. 去重：
   • 算出来的 answer 是该连通子图中所有圆点的数量。
   • 题目要求摧毁的是 小 C 没占领 的城市，所以答案减去 $k$（即 $|S|$）。

3. 代码细节注释

// ... 头文件和模板 ...

// 变量定义
// eu, ev: 存储边的端点
// adj: 原图邻接表 -> 后来清空作为圆方树邻接表 (rsq)
// rsq: 圆方树邻接表 (代码中似乎复用了 adj 或者是另外定义的，看下文 rsq 确实定义了)
vector<int> rsq[N]; // 实际用的圆方树邻接表

// Tarjan 算法构建圆方树
void dfs(int u, int p) {
    num[u] = low[u] = ++timer;
    sta.push(u);

    for (int id : adj[u]) // 遍历原图的边
        if (id != p) {
            int v = eu[id] ^ ev[id] ^ u; // 获取边的另一个端点

            if (num[v])
                minimize(low[u], num[v]);
            else {
                dfs(v, id);
                minimize(low[u], low[v]);

                if (low[v] >= num[u]) { // 发现点双
                    square++; // 新建方点
                    // 将点双内的点弹出，连接到方点
                    while (int c = sta.top()) {
                        rsq[c].push_back(square + n);
                        rsq[square + n].push_back(c);
                        sta.pop();
                        if (c == v) break;
                    }
                    // u 也是点双的一部分，连接但不弹出
                    rsq[u].push_back(square + n);
                    rsq[square + n].push_back(u);
                }
            }
        }
}

// ... LCA 和 树上倍增 ...

// 圆方树上的 DFS，处理深度和倍增
void work(int u, int p) {
    tin[u] = ++timer;
    for (int v : rsq[u])
        if (v != p) {
            // 关键：只有圆点 (v <= n) 贡献权值 1，方点贡献 0
            dep[v] = dep[u] + (v <= n);
            par[v][0] = u;
            // ... 倍增处理 ...
            work(v, u);
        }
    tout[u] = timer;
}

// ... lca 函数 ...

void process() {
    // 1. 构建圆方树
    timer = 0;
    dfs(1, -1);
    
    // 2. 预处理 LCA 和 dep
    timer = 0;
    work(1, -1); // 根节点是 1，是圆点，初始 dep 应由 1 开始计算吗？
    // 注意：work 里 dep[v] = dep[u] + ...，根节点的 dep 需要在调用前或内部正确初始化。
    // 由于全局变量初始化为0，dep[1] 默认为 0 (如果它被当做子节点处理会加1)。
    // 这里 dep 计算的是“路径上除根节点外的圆点数”或者代码逻辑自洽即可。
    // 实际上代码中 dep[1] = 0。但这不影响距离差分计算。

    while (q--) {
        int k; cin >> k;
        vector<int> terminal(k);
        for (int i = 0; i < k; i++) cin >> terminal[i];

        // 按 DFS 序排序，围成一圈
        sort(all(terminal), [&](int u, int v) {
            return tin[u] < tin[v];
        });

        int answer = 0;
        for (int i = 0; i < k; i++) {
            int j = (i + 1) % k;
            // 计算两点间路径权值
            // 公式：dep[u] + dep[v] - 2*dep[LCA]
            // 这计算的是 u 到 v 路径上圆点的数量，但不包括 LCA (如果 LCA 是圆点)
            answer += dep[terminal[i]] + dep[terminal[j]] - 2 * dep[lca(terminal[i], terminal[j])];
        }

        answer /= 2; // 每一条边被算了两遍

        // 补回最顶端 LCA 的贡献
        // terminal[0] 和 terminal.back() 的 LCA 就是整个点集的 LCA
        if (lca(terminal[0], terminal.back()) <= n)
            answer++; 

        // 减去被占据的城市数量
        cout << answer - k << endl;
    }
    
    // ... 清空数组，用于多组数据 ...
}

4. 复杂度分析

• 构建圆方树：$O(N + M)$。
• LCA 预处理：$O(N \log N)$。
• 单次询问：$O(K \log K + K \log N)$（排序 + $K$ 次 LCA）。
• 总时间复杂度：$O(T \times (\sum |S| \log N + N \log N))$，足以通过本题数据范围。