我们要在一棵以节点 1 为根、共有 $n$ 个节点的树上，从根出发遍历整棵树并回到根，同时希望所有节点的完成时间的最大值最小。对于每个节点 $i$，它第一次被访问的时刻记为 $r_i$，非根节点的完成时间为 $r_i + a_i$，根节点返回时刻为整条路径长度 $L=2(n-1)$，因此根的完成时间为 $L + a_1$。

本质上，我们需要优化这条“树的欧拉回路”的遍历顺序，使得最迟完成的节点尽可能早地完成。为此，我们引入树形动态规划。

令 $f(u)$ 表示从进入节点 $u$ 时刻记作 0 开始，完成其整个子树内所有节点的最大相对时间，$size_u$ 表示以 $u$ 为根的子树节点数。

初始化时，节点 $u$ 自身在时刻 0 就被访问，完成时间为 $a_u$，故 $f(u)=a_u$。对每个子节点 $v$ 递归地计算出 $f(v)$ 和 $size_v$ 之后，我们要决定遍历这些子树的先后顺序。

子树中若接连选取相邻两项 $v_1,v_2$，那么答案为：

反转 $v_1,v_2$ 后的两项为

注意到 $1+f(v_1)$ 与 $1+f(v_2)$ 不会成为答案，将其余两项作差得将 $f(v)-2siz_v$ 从小到大排序，这一策略能最小化 $f(u)$。

实现时，我们先在一次 DFS 中累积每个子树的来回耗时，用于计算 $f(u)$ 的累加部分；然后将每个子树对应的 $f(v)-2siz_v$ 排序，遍历已排序的子树更新 $g(u)$。对于根节点 $1$，还要将全局路径长度 $2(n-1)$ 加上 $a_1$ 与 $f(1)$ 取最大，作为最终答案：