题目概述

给定一棵 $n$ 个节点的树，需要找出若干条边不相交的路径，使得这些路径的总边数最大。路径可以是任意长度（包括0），但必须满足：

1. 路径之间不能共享边
2. 路径可以共享节点

核心思路

这是一道树形DP题目，使用动态规划在树上进行状态转移，计算以每个节点为根的子树中的最优解。

状态定义

定义 f[u][0..3] 表示以节点 u 为根的子树中的不同状态：

• f[u][0]: 在子树中选取若干条边不相交的路径，且存在一条以 u 为端点向上延伸的链（这条链还未闭合）
• f[u][1]: 在子树中选取若干条边不相交的路径，且存在一条完全在子树内部、LCA 为 u 的完整链
• f[u][2]: 在子树中选取若干条边不相交的路径，且存在一条完整链 + 一条向上链（两条链在 u 处连接）
• f[u][3]: 在子树中选取若干条边不相交的路径，且存在一条完整链（LCA 不在 u）

ans 记录全局最优答案。

算法流程

1. 初始化

• f[u][0] = 0（初始没有边）
• f[u][2] = -inf（初始不可行）

2. 第一遍遍历子节点

for (int i : v[u]) {
    if (i == fa) continue;
    dfs(i, u);
    f[u][0] = max(f[u][0], f[i][0]);  // 继承子节点的向上链
    f[u][2] = max(f[u][2], f[i][2] + w - 2);  // 从子节点转移 f[2]
}
f[u][0] += max(w - 2, 0);  // u 节点贡献的边数

3. 统计子节点信息

维护 mx[0..3] 记录子节点 f[i][0] 的最大四个值，用于后续组合路径。

4. 计算状态转移

• f[u][1]: 两条最大的向上链在 u 处连接形成完整链

  f[u][1] = mx[0] + mx[1] + w;
  

• f[u][2]: 多种情况取最大值：

  1. 从子节点直接转移
  2. 子节点的 f[i][3] 加上 u 的贡献
  3. 三条向上链在 u 处组合
  4. 与其他状态组合

• f[u][3]: 子节点中 f[i][1] 或 f[i][3] 的最大值

5. 更新全局答案 ans

在 DP 过程中，不断用以下情况更新答案：

1. 两条完整链（f[i][3]）组合
2. 两条完整链（f[i][1]）组合
3. 四条向上链在 u 处组合
4. 各种子节点状态与当前节点组合

时间复杂度

• 每个节点访问一次，每个节点的子节点遍历常数次
• 总时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

代码特点

1. 输入参数 X: 题目可能有多组测试数据，X 控制是否读取额外无用数据
2. 高效的状态转移: 通过维护最大值、次大值等，避免 $O(k^2)$ 的枚举
3. 边界处理: 注意处理 w-2 可能为负数的情况

样例解释

对于一棵树，算法会找到边不相交路径的最大集合。例如：

• 如果树是一条链，最优解就是整条链本身
• 如果树是星形，最优解可能选择多条从中心出发的路径

注意事项

1. 路径必须边不相交，但可以共享节点
2. 路径长度可以为 0（单点）
3. 需要仔细处理各种状态的组合情况