虽然是猜的，但是你确定这是黑题吗？

Mini_PEKKA · 2025-12-26 22:29:49 · 题解

很直接的做法。

不妨令 1 为根。令 f_i 为 i 的父亲，c_i 为 (i,f_i) 这条边被多少条路径覆盖。猜测答案为 \displaystyle\sum_{i=2}^n\min(c_i,2)。

构造方案的过程大概是每次选出一条路径并确定其方向。

具体地，我们只需关心期望贡献为 2 但是当前贡献 <2 的边，称其为当前的关键边。

如果这些边中存在一条边恰好被一条未定向路径覆盖，就给这条路径定向使得这条边贡献为 2。

否则随便选一条未定向路径并随便定向。

时间复杂度为 \mathcal{O}((n+m)m)。Code

基于答案式子的正确性证明：只用证明“否则”的情况的选择一定不劣。考虑对于所有未定向路径，如果存在一种定向方案达到最优情况（当前每条关键边都被某条未定向路径向上经过且被某条未定向路径向下经过），那么把该方案中所有方向反过来也可以达到最优情况。所以任意一条路径无论怎么定向都一定在某个最优方案中。