题目概述

有 $n$ 个城市，$m$ 条双向道路，形成一个连通图。每个居民要访问其他所有居民一次，总共需要 $n(n-1)$ 次会面。

如果封锁一个城市，那么这个城市无法被访问，也无法通过该城市访问其他城市。我们需要计算封锁每个城市时，无法进行的会面次数。

---

问题分析

关键观察

1. 图的连通性：原图是连通的，但封锁一个城市后图可能变得不连通
2. 会面计数：两个居民能会面当且仅当他们在封锁后的图中连通
3. 问题转化：对于每个城市 $i$，计算封锁它后，所有不连通的点对数量

数学形式化

设封锁城市 $i$ 后，图分裂成若干个连通分量，大小分别为 $s_1, s_2, \dots, s_k$。

那么无法进行的会面次数为：

$$\text{ans}[i] = n(n-1) - \sum_{j=1}^k s_j(s_j-1)$$

因为原本有 $n(n-1)$ 次会面，封锁后只剩下各个连通分量内部的会面。

---

算法思路

使用割点理论

这个问题本质上是在求：对于每个点，删除它后图分裂成的各个连通分量的大小。

这正好是Tarjan算法求割点时能够计算的信息。

Tarjan算法回顾

在DFS遍历图时，维护：

• dfn[u]：DFS序（时间戳）
• low[u]：通过回边能回到的最早祖先

点 $u$ 是割点当且仅当：

• 如果 $u$ 是根节点，且有多于1个子树
• 如果 $u$ 不是根节点，且存在子节点 $v$ 满足 low[v] >= dfn[u]

计算答案

在Tarjan算法过程中，对于每个点 $u$：

如果 $u$ 不是割点

封锁 $u$ 只会影响直接经过 $u$ 的会面：

• $u$ 无法与其他 $n-1$ 个点会面
• 其他 $n-1$ 个点无法与 $u$ 会面
• 总共 $2(n-1)$ 次会面无法进行

如果 $u$ 是割点

封锁 $u$ 后，图会分裂成多个连通分量。

设删除 $u$ 后产生的连通分量大小为 $s_1, s_2, \dots, s_k$，那么无法进行的会面次数为：

$$\text{ans}[u] = n(n-1) - \sum_{j=1}^k s_j(s_j-1)$$

在Tarjan过程中，当我们发现 $v$ 满足 low[v] >= dfn[u] 时，以 $v$ 为根的子树就是一个连通分量，大小为 siz[v]。

---

算法详解

核心代码解析

数据结构

int dfn[N], low[N], sn;        // DFS序相关
long long ans[N], siz[N];      // 答案和子树大小
int cut[N];                    // 标记是否为割点

Tarjan算法

void tarjan(int u, int last) {
    dfn[u] = low[u] = ++sn, siz[u] = 1;
    int son = 0, v, sum = 0;
    
    for (int i = head[u]; i; i = e[i].ne) {
        if (i == (last ^ 1)) continue;  // 避免重复访问父边
        
        v = e[i].v;
        if (!dfn[v]) {
            tarjan(v, i);
            siz[u] += siz[v];           // 累加子树大小
            low[u] = min(low[u], low[v]);
            
            if (low[v] >= dfn[u]) {     // 发现割点条件
                if (u != root || ++son > 1) cut[u] = 1;
                ans[u] += siz[v] * (n - siz[v]);  // 累加这个分量的贡献
                sum += siz[v];          // 记录已处理的子树大小
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
    
    // 最终处理答案
    if (!cut[u]) {
        ans[u] = 2LL * (n - 1);         // 非割点情况
    } else {
        // 割点情况：还要加上剩余部分（包含父节点那边的分量）
        ans[u] += 1LL * (n - sum - 1) * (sum + 1) + (n - 1);
    }
}

答案计算原理

对于割点 $u$：

• ans[u] += siz[v] * (n - siz[v])：分量 $siz[v]$ 与图中其他点的点对
• (n - sum - 1) * (sum + 1)：父节点那边的分量与已处理分量的点对
• (n - 1)：$u$ 本身与其他点的会面

---

样例解析

样例输入

5 5
1 2
2 3
1 3
3 4
4 5

图结构：三角形1-2-3，加上链3-4-5。

计算结果

• 城市1,2,5：不是割点，答案 $2×(5-1)=8$
• 城市3：割点，删除后分成 {1,2} 和 {4,5}，答案 $20 - (2+2) = 16$
• 城市4：割点，删除后分成 {1,2,3} 和 {5}，答案 $20 - (6+0) = 14$

输出：

8
8
16
14
8

---

复杂度分析

• 时间复杂度：$O(n + m)$
  • Tarjan算法每个点和边只访问一次
• 空间复杂度：$O(n + m)$
  • 存储图和算法所需数组

---

总结

这道题的关键在于：

1. 问题转化：将会面次数问题转化为图连通性问题
2. 割点理论：利用Tarjan算法识别割点并计算删除后的连通分量
3. 组合计数：通过连通分量大小计算受影响的点对数量
4. 高效算法：在DFS过程中同时完成所有计算，达到线性复杂度

这种"图论+组合计数"的问题在竞赛中很常见，Tarjan算法是解决这类问题的有力工具。