题目分析

本题要求用两台吹雪机清理树上的所有边，每条边至少被清理一次，目标是使得两台吹雪机行进的总路程最短。

关键观察：由于每条边至少被清理一次，如果每条边只被清理一次，总路程就是所有边权之和的两倍（因为两台机器各自走一遍）。但通过让两条路径共享某些边，可以减少总路程。

算法思路

核心思想：树形DP + 状态压缩

状态设计：

• dp[u][i][j]：表示在以节点 u 为根的子树中，状态为 i，标志为 j 时的最小代价
• i ∈ [0,4]：表示子树中路径端点的使用情况
• j ∈ {0,1}：表示是否有路径延伸到父节点

状态含义详解

状态 i 的含义：

• i = 0：子树中没有路径端点
• i = 1：子树中有1个路径端点
• i = 2：子树中有2个路径端点
• i = 3：子树中有3个路径端点
• i = 4：子树中有4个路径端点

标志 j 的含义：

• j = 0：没有路径延伸到父节点
• j = 1：有路径延伸到父节点

状态转移

对于每个节点 u 和它的子节点 v，考虑所有可能的状态组合：

for (int tp = 0; tp < 2; tp++)        // 是否走当前边
for (int s = 0; s <= 4; s++)          // 子节点状态
for (int k = 0; k < 2; k++)           // 子节点标志
for (int j = 0; j <= 4; j++)          // 当前节点状态  
for (int rk = 0; rk < 2; rk++) {      // 当前节点标志
    int bad = s + j + (k ^ tp ^ 1);   // 检查状态是否合法
    int nans = dp[u][j][rk] + dp[v][s][k];
    int nflp = rk ^ 1 ^ tp;
    
    if (tp) nans += d;  // 如果走这条边，加上边权
    
    if (bad > 4) continue;  // 状态不合法
    
    chkmin(nw[bad][nflp], nans);
}

关键技巧

1. 状态合并验证：通过 bad = s + j + (k ^ tp ^ 1) 来确保合并后的状态不超过限制（最多4个端点）

2. 边权计算：只有当 tp = 1（即走这条边）时才加上边权 d

3. 标志位更新：nflp = rk ^ 1 ^ tp 根据当前选择更新是否延伸到父节点

代码结构

1. 数据结构

vector<pi> eg[maxn];  // 邻接表存储树
int dp[maxn][5][2];   // DP状态数组
int nw[5][2];         // 临时数组用于状态转移

2. 核心DFS过程

void dfs(int a, int fa) {
    // 初始化当前节点状态
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 2; j++)
            dp[a][i][j] = 1e9;
    dp[a][0][0] = 0;
    
    // 遍历所有子节点
    for (auto [v, d] : eg[a]) {
        if (v == fa) continue;
        dfs(v, a);
        
        // 状态转移
        // ... (详细转移逻辑)
    }
}

3. 答案计算

int ans = 1e9;
for (int i = 0; i <= 4; i++)
    for (int j = 0; j < 2; j++) {
        int nb = i + (j % 2);
        if (nb <= 4)
            chkmin(ans, dp[1][i][j]);
    }
cout << ans + sum << endl;  // 加上基础边权和

算法正确性证明

基础代价：sum 是所有边权之和，表示每条边至少被走一次的代价。

优化部分：通过DP找到最优的路径共享方案，减少重复走的边。

状态设计合理性：状态 i 准确记录了路径端点的使用情况，确保不会超过两台机器的承载能力（最多4个端点）。

复杂度分析

时间复杂度：O(n × 5 × 2 × 5 × 2) = O(100n)，对于 n ≤ 100,000 可以接受

空间复杂度：O(n × 5 × 2) = O(10n)，在限制范围内

样例验证

样例1：

• 输入：7个节点，边权和 = 2+3+1+1+2+4 = 13
• 输出：15 = 13 + 2（最优共享方案）

样例2：

• 输入：4个节点，边权和 = 1+2+3 = 6
• 输出：6 = 6 + 0（无法进一步优化）

该算法通过精细的状态设计和树形DP，成功解决了树上两条路径覆盖的最优化问题。