题意回顾

给定一棵 $n$ 个节点的树，边带权（权值可为负）。
要选出若干条长度恰好为 $4$ 的简单链（即包含 $5$ 个节点、$4$ 条边），且这些链在点上不相交（边自然也不相交）。
目标是最大化所选链的边权总和。

数据范围：$n \leq 2\times 10^5$，边权绝对值 $\leq 10^9$。

---

关键难点

1. 长度恰好为 4：这意味着一条链涉及 5 个节点，在树上形态比较固定。
2. 链不交：选择的链不能共享节点，是点不交路径覆盖的一种特殊情形。
3. 边权可负：需要判断选一条链是否划算。

---

树形 DP 状态设计

由于链长度固定为 $4$，我们可以枚举链在树上的形态。长度为 $4$ 的链在树上有两种主要形态：

• 直链：$u_0 - u_1 - u_2 - u_3 - u_4$（5 个节点依次相连）
• 星形链：长度 4 的链在树上只能是直链形态，因为树没有环。

所以唯一形态就是 5 个节点连成一条线。

---

DP 思路

设 $dp[u][t]$ 表示在 $u$ 的子树中，$u$ 所处的链的未完成部分长度为 $t$ 时的最大收益。

这里 $t$ 的含义：

• $t=0$：$u$ 不在任何链中，或 $u$ 是某条完整链的端点（链已结束）
• $t=1$：$u$ 是某条链的一端，该链已包含 1 条边（还需 3 条边完成）
• $t=2$：$u$ 是某条链的一端，该链已包含 2 条边（还需 2 条边完成）
• $t=3$：$u$ 是某条链的一端，该链已包含 3 条边（还需 1 条边完成）
• $t=4$：$u$ 是某条链的一端，该链已包含 4 条边（链完成）

由于链长恰好 4，所以 $t$ 取值 $0,1,2,3,4$。

---

状态转移

考虑节点 $u$ 和它的一个子节点 $v$，边权 $w$。

1. 不将边 $(u,v)$ 用于链

那么 $v$ 的子树独立处理，$u$ 的状态不变，加上 $v$ 子树的最佳收益（即 $dp[v][0]$）。

2. 将边 $(u,v)$ 用于延长链

• 如果 $u$ 当前状态为 $t$，加入这条边后状态变为 $t+1$（如果 $t<4$）
• 收益增加 $w$
• 同时 $v$ 的状态要从 $t'$ 转移来，且 $u$ 与 $v$ 的状态要匹配

更具体地，枚举 $u$ 的状态 $i$ 和 $v$ 的状态 $j$，尝试用边 $(u,v)$ 连接：

• 如果 $i=0, j=3$：用这条边连接后形成完整链（$0\to 1\to 2\to 3\to 4$ 在 $v$ 子树中已完成 3 条边，加上 $(u,v)$ 完成第 4 条），收益 $w + dp[v][3]$，$u$ 新状态为 $0$（链完成）。
• 如果 $i=1, j=2$：连接后状态变为 $4$（完成链），收益 $w + dp[v][2]$，$u$ 新状态 $0$。
• 如果 $i=2, j=1$：同理，收益 $w + dp[v][1]$，$u$ 新状态 $0$。
• 如果 $i=3, j=0$：收益 $w + dp[v][0]$，$u$ 新状态 $0$。

以及未完成链的延长：

• $i=0, j=0$：开始新链，$u$ 状态变为 $1$，收益 $w + dp[v][0]$
• $i=1, j=0$：延长链，$u$ 状态变为 $2$，收益 $w + dp[v][0]$
• $i=2, j=0$：$u$ 状态变为 $3$，收益 $w + dp[v][0]$
• $i=3, j=0$：$u$ 状态变为 $4$，收益 $w + dp[v][0]$

---

合并多个子树

节点 $u$ 可能有多个子节点，我们需要合并它们的贡献。
因为链不能分叉，所以 $u$ 最多连接两个子节点用于同一条链（作为链上的一个点有度最多 2）。

实际上，$u$ 在一条链中最多连接 2 个子节点（一进一出），其他子节点必须独立处理。

因此合并时，对每个子节点 $v$，我们考虑：

• 不连接 $(u,v)$：贡献 $dp[v][0]$
• 连接 $(u,v)$ 并延长链：根据当前 $u$ 状态和 $v$ 状态更新

这是一个经典的树形 DP 合并技巧，需要维护 $u$ 的各个状态的最大值，并依次用每个子节点更新。

---

算法步骤

1. 任选根节点（如 1）进行 DFS
2. 初始化 $dp[u][0]=0$，其余 $dp[u][t]=-\infty$
3. 对 $u$ 的每个子节点 $v$（边权 $w$）：
   • 创建临时数组 $new\_dp$ 初始为 $-\infty$
   • 枚举 $u$ 的当前状态 $i$ 和 $v$ 的可能状态 $j$，考虑：
     • 不连接：$new\_dp[i] = \max(new\_dp[i], dp[u][i] + dp[v][0])$
     • 连接并可能完成链：根据上述规则更新
   • 将 $new\_dp$ 复制给 $dp[u]$
4. 最终答案：$\max(dp[root][0], dp[root][4])$（$t=4$ 表示以 root 为端点的完整链）

---

复杂度分析

• 状态数：每个节点 $5$ 个状态
• 合并时枚举 $i,j$：$5\times 5=25$ 次
• 总复杂度：$O(25n) = O(n)$，可过 $n\leq 2\times 10^5$

---

总结

本题的关键在于：

1. 识别链长固定为 $4$ 的特殊性
2. 设计状态 $dp[u][t]$ 表示 $u$ 在链中的位置
3. 分类讨论连接边是否用于链，以及是否完成链
4. 使用临时数组正确合并多个子树的贡献

通过精细的状态设计和转移，可以在 $O(n)$ 时间内求出最大收益，解决大规模数据。