题目理解

我们有一棵 $n$ 个节点的树，根节点是 $1$ 号房屋。
Bajtazar 从根节点出发，遍历整棵树送电脑，每条边最多走两次（去一次，回一次）。
每到一个节点放下电脑，该节点立即开始安装游戏（耗时 $c_i$）。
Bajtazar 送完所有电脑后回到根节点，他自己也开始安装游戏（耗时 $c_1$）。
我们要最小化 所有人完成安装的时间 的最大值。

关键点

1. 树结构：任意两点间唯一路径。

2. 遍历性质：每条边最多往返一次（即最多走两次），实际上 DFS 遍历树每条边就是走两次（除了最后一次返回可能省略）。

3. 时间计算：

   • 到达节点 $u$ 的时间 = 从根出发到 $u$ 的路径长度（分钟）
   • 该节点完成安装的时间 = 到达时间 + $c_u$
   • 最终答案是所有节点完成时间的最大值（包括根节点在自己返回后的安装时间）。

4. 顺序影响：对于某个子树，先访问哪个分支会影响该子树内节点的完成时间，因为 Bajtazar 在子树间切换需要来回走边。

思路

这是一个树形 DP + 贪心排序问题。

状态设计

设 $dp[u]$ 表示从进入 $u$ 子树开始，到该子树所有节点安装完成并且 Bajtazar 回到 $u$ 的最小可能的最大完成时间（相对时间）。

转移思路

对于节点 $u$，假设它有若干子节点 $v_1, v_2, \dots, v_k$。

• 从 $u$ 到 $v_i$ 需要 1 分钟，访问 $v_i$ 子树并返回 $u$ 需要 $dp[v_i]$ 时间（注意 $dp[v_i]$ 已经包含了来回时间）。
• 但是，在访问 $v_i$ 子树之前，$u$ 已经花费了一些时间访问其他子树，所以 $v_i$ 子树的完成时间要加上之前的时间。

如果我们按某个顺序访问子节点 $v_1, v_2, \dots, v_k$，那么：

• 访问 $v_1$ 的完成时间：$1 + dp[v_1]$
• 访问 $v_2$ 的完成时间：$(1 + dp[v_1]) + 1 + 1 + dp[v_2]$ （因为从 $v_1$ 回到 $u$ 再走到 $v_2$）
• 一般地，访问 $v_j$ 的完成时间：$2(j-1) + 1 + dp[v_j]$ （$2(j-1)$ 是之前来回的累计时间，$+1$ 是去 $v_j$ 的时间）

因此，对于顺序 $v_1, v_2, \dots, v_k$，$v_j$ 子树的完成时间是： [ \text{finish}[v_j] = 2(j-1) + 1 + dp[v_j] ] 我们要最小化 $\max_{j} \text{finish}[v_j]$。

贪心排序

为了最小化最大值，应该按照 $dp[v]$ 降序 访问子节点，因为 $dp[v]$ 大的子树应该尽早访问，减少它们因等待而增加的时间。

所以：

1. 计算所有子树的 $dp[v]$。
2. 按 $dp[v]$ 从大到小排序。
3. 计算： [ dp[u] = \max_{j=1..k} \big( 2(j-1) + 1 + dp[v_j] \big) ] 同时，还要考虑 $u$ 本身的安装时间 $c_u$，因为 Bajtazar 可能在访问子树前或后放下电脑给 $u$。实际上，通常是在访问子树前放下电脑给 $u$，所以 $u$ 的完成时间是 $0 + c_u$（如果 $u$ 是根则不同）。

根节点的特殊处理

根节点 $1$ 是在最后返回时才安装游戏，所以它的完成时间是： [ \text{总遍历时间} + c_1 ] 总遍历时间就是 $dp[1]$（因为 $dp[1]$ 定义为从进入 1 开始到回到 1 的时间，但 1 一开始就进入，所以遍历完所有子树回到 1 的时间就是 $dp[1]$）。

因此最终答案是： [ \max\big( dp[1],; \max_{u \neq 1} (\text{dist}(1,u) + c_u) \big) ] 其中 $\text{dist}(1,u)$ 是 1 到 $u$ 的距离（到达时间）。

算法步骤

1. 读入 $n, c[1..n]$ 和树结构。
2. DFS 从根 1 开始：
   • 对每个节点 $u$，收集子节点的 $dp[v]$。
   • 对子节点按 $dp[v]$ 降序排序。
   • 计算 $dp[u] = \max( c[u],\; \max_j ( 2(j-1) + 1 + dp[v_j] ))$。
     • 注意：对于非根节点，$c[u]$ 是在到达 $u$ 时开始安装的，所以完成时间是 $\text{到达时间} + c[u]$，但 $dp[u]$ 是相对时间，所以比较时要小心。实际上更常见的写法是 $dp[u] = \max( \text{子树的完成时间}, c[u] )$ 但需要仔细处理时间线。
3. 最终答案 = $\max( dp[1] + c[1]? )$ 需要根据定义调整。

实际上常见解法是： 设 $f[u]$ = 从进入 $u$ 开始到该子树所有人安装完成并回到 $u$ 的最小可能最大完成时间（绝对时间从 0 开始）。 那么：

• 到达 $u$ 的时间已知（DFS 参数）。
• 对子节点按某种规则排序后计算。

算法标签

• 树形动态规划 (Tree DP)
• 贪心排序 (Greedy Sorting)
• DFS 遍历
• 最优化问题

复杂度

• 排序子节点：$O(\text{deg}(u) \log \text{deg}(u))$，总 $O(n \log n)$
• DFS：$O(n)$
• 总复杂度：$O(n \log n)$，可过 $n \le 5\times 10^5$

样例验证

样例中：

• 正确输出 11
• 按上述贪心方法可得 11

最终算法标签： 树形DP 贪心算法 DFS 排序优化