题目理解

我们有一棵 $n$ 个节点的树（$n-1$ 条边）。游行路线是树上的一条简单路径（不重复经过边）。在每个经过的路口，需要对未被游行使用的街道入口设置路障。

关键：如果一个路口有 $d$ 条边相连，游行路线使用了其中的 $k$ 条边（$k=1$ 或 $2$），那么需要设置 $d-k$ 个路障。

问题转化

设游行路径为 $P$，总路障数为：

$$\text{barriers}(P) = \sum_{u \in P} (\text{deg}(u) - \text{used\_edges}(u)) $$

其中：

• $\text{deg}(u)$ 是节点 $u$ 的度数
• $\text{used\_edges}(u)$ 是路径 $P$ 在节点 $u$ 使用的边数：
  • 端点：使用 1 条边
  • 中间点：使用 2 条边

所以：

$$\text{barriers}(P) = \sum_{u \in P} \text{deg}(u) - (2|P| - 2) $$

因为路径有 $|P|$ 个节点，使用 $|P|-1$ 条边，每条边在两端各算一次，总共 $2(|P|-1)$ 次边使用。

关键观察

问题转化为：找到一条路径 $P$，使得 $\sum_{u \in P} \text{deg}(u) - 2|P| + 2$ 最大。

令 $w(u) = \text{deg}(u) - 2$，则目标函数为：

$$\sum_{u \in P} w(u) + 2$$

因此，问题等价于在树上找一条路径，使得路径上节点的 $(deg-2)$ 之和最大。

算法思路

1. 树形DP定义

$f[u]$：从 $u$ 出发往子树方向走，能够获得的最大 $\sum (deg-2)$ 值。

2. 状态转移

对于节点 $u$，考虑所有子节点 $v$：

• 从 $u$ 出发往某个子树 $v$ 延伸：$f[u] = \max(deg[u]-2, \max_v f[v] + deg[u]-2)$

3. 更新答案

两种情况：

1. 单链：$f[u]$ 本身
2. 双链：选择两个子树的链拼接，经过 $u$

对于双链：$ans = \max(ans, mx1 + mx2 + deg[u] - 4)$

• $mx1$, $mx2$ 是最大的两个 $f[v]$ 值
• 减 4 是因为 $u$ 的 $deg-2$ 被重复计算了两次

代码详解

inline void dfs(int u, int fa) {
    int mx1 = 0, mx2 = 0, cnt = 0;
    f[u] = otd[u];  // 初始化为度数
    
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (v == fa) continue;
        
        cnt++;
        dfs(v, u);
        mx2 = max(f[v], mx2);
        if (mx2 > mx1) swap(mx1, mx2);
    }
    
    // 单链：选择最好的子树延伸
    if (cnt) 
        f[u] = max(f[u], mx1 + otd[u] - 2);
    
    // 双链：拼接两条子树链
    if (cnt >= 2) 
        ans = max(ans, mx1 + mx2 + otd[u] - 4);
    
    ans = max(ans, f[u]);  // 单链答案
}

4. 初始化

for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    otd[u]++;  // 记录度数
    otd[v]++;
    add_Edge(u, v);
    add_Edge(v, u);
}

5. 最终答案

printf("%d\n", min(n - 2, ans));

• 因为路径至少有两个节点，最多 $n$ 个节点
• 路障数不会超过 $n-2$（当路径包含所有节点时）

正确性分析

1. 单链情况：$f[u]$ 记录了从 $u$ 出发的最优链
2. 双链情况：通过维护最大的两个 $f[v]$ 值，找到经过 $u$ 的最优路径
3. 度数处理：$deg[u]-2$ 的调整正确处理了端点和中间点的差异

时间复杂度

• DFS遍历：$O(n)$
• 总复杂度：$O(n)$

算法标签

• 树形动态规划
• DFS
• 树链
• 贪心优化

总结

这道题的关键在于将路障计数问题转化为树上带权路径最大值问题。通过巧妙的权重设计 $(deg-2)$ 和树形DP，我们能够在 $O(n)$ 时间内找到最优解。算法结合了树的直径求解思想和度数的组合计算，体现了树形DP的典型应用。