题目重述（E. Kia Bakes a Cake）

我们有：

• 一棵 $n$ 个节点的树 $T$
• 一个长度为 $n$ 的二进制串 $s$，$s_i=1$ 表示节点 $i$ 被选中
  被选中的节点集合记为 $V'$，$|V'| = k$

根据被选中的节点 $V'$ 构造一个完全图：

• 节点集 = $V'$
• 边权 $w(u,v)$ = 树 $T$ 中 $u$ 到 $v$ 的唯一路径上的边数（即树上距离）

一条路径 $v_1, v_2, \dots, v_m$（顶点来自 $V'$） 是 nice，如果： [ 2 \cdot w(v_i, v_{i+1}) \le w(v_{i+1}, v_{i+2}) \quad \text{对所有 } 1 \le i \le m-2 ]

即：路径上每一条边的权值至少是上一条边的两倍（严格来说，至少两倍）。

对每个 $i \in V'$，要求：从 $i$ 出发的 nice 简单路径，最长能有多长（即 $m$ 的最大值）。

若 $i \notin V'$，输出 $-1$。

---

1. 问题转化与关键观察

1.1 树上距离

树上两点距离 = 它们唯一路径上的边数。
因为树是连通的简单图，没有环，所以 $w(u,v)$ 可以快速计算。

1.2 Nice 路径的条件

设边权序列为 $d_1, d_2, \dots, d_{m-1}$，其中 $d_j = w(v_j, v_{j+1})$。

nice 条件： [ d_{i+1} \ge 2 \cdot d_i \quad \forall i ]

即权值至少翻倍增长。

1.3 权值的范围

树上任意两点的距离 ≤ $n-1$。
所以 $d_i \in [1, n-1]$。但翻倍条件意味着最大长度是 $\log_2(n-1)$ 级别（大约 $\lg n$）。

因此，实际上 $m \le O(\log n)$，因为翻倍太快，很快就超出 $n-1$ 了。

---

2. 动态规划思路（分层 DP）

设 $dp[k][v]$ 表示：从 $v$ 出发，存在一条长度为 $k$ 的 nice 路径（即 $m = k+1$ 个节点），且该路径的第一条边权值 $\le$ 某个上界？
但标程里 $dp[k][v]$ 的定义是：从 $v$ 出发的最大 nice 路径长度？不，是 $dp[lev][v]$ = 以 $v$ 为起点，长度为 $2^{lev}$ 的 nice 路径的最大可能步数？其实标程里 $dp[k][v]$ 存的是最大长度（顶点数）。

关键：
$dp[lev][v]$ = 以 $v$ 为起点，nice 路径最大能到达的距离（步数？节点数？）。
看标程输出时：对每个 $v$，找最大的 $lev$ 使得 $dp[lev][v] \ge 1$，然后输出 $lev+1$（路径节点数）。所以 $dp[lev][v]$ 应该是路径的长度（边数）？其实他直接输出 $lev+1$，那 $lev$ 就是路径的边数 - 1？其实 $lev$ 是步数级别。

为了不混淆，我们直接按标程逻辑：
$dp[0][v] = 2n$ 如果 $s_v=1$，否则 $-1$。
这里 $2n$ 只是一个很大的初始值，表示从 $v$ 可以走至少 0 步（起点）。

然后迭代：从 $dp[k-1]$ 计算 $dp[k]$，表示从 $v$ 出发，nice 路径中第一条边权值在某个范围内。

---

3. 树形 DP + 重心分解

3.1 树上 DP 难点

nice 路径可以跨越不同子树，需要处理“两条边的权值比较”。
$w(a,b)$ 受树结构影响，不是简单的深度差。

但 $w(a,b) = h[a] + h[b] - 2h[lca(a,b)]$，其中 $h$ 是深度。

如果两条边为 $a \to b$ 和 $b \to c$，nice 条件： [ 2\big(h[a] + h[b] - 2h[lca(a,b)]\big) \le h[b] + h[c] - 2h[lca(b,c)] ] 这很复杂。

解决办法：用重心分解。
对每个子树的根（重心），将来自不同子树的点配对，在重心处计算两条边权值。

---

3.2 中心分解的目的

以重心 $g$ 为分界点，路径 $a \to g \to c$：
$w(a,g) = h[a] + h[g] - 2h[lca(a,g)]$
$w(g,c) = h[g] + h[c] - 2h[lca(g,c)]$

如果 $a$ 和 $c$ 在不同子树，$lca(a,g) = g$？不一定，因为 $g$ 是重心，但 $a$ 可能和 $g$ 有不同 LCA。

这样还是复杂。标程用的方法是：

• 对每个重心 $g$，跑 DFS，对当前子树记录当前节点 $v$ 的深度 $h[v]$，以及 $T[v]$ 从 $g$ 出发的最大步数。
• 但 $T[v]$ 其实是 $dp[k-1][v]$ 的值，表示从 $v$ 出发到某点的最大步数。

这样，对于边 $g \to v$ 和 $v \to u$，nice 条件： [ 2 \cdot w(g,v) \le w(v,u) ] $w(g,v) = h[v]$（如果 $g$ 是 $\text{lca}$）。但 $v$ 与 $u$ 的 LCA 可能不是 $g$，所以 $w(v,u)$ 不是简单的 $h[v]+h[u]$。

所以标程用了更巧妙的处理：
在重心 $g$ 处，给每个子树 $S$ 的节点 $x$ 标记 $tag[x] = \text{子树的代表}$，然后对 $x$，我们想找之前子树的节点 $y$ 满足 $2h[y] \le h[x] + h[y] - 2h[lca(x,y)]$？不是，其实是 $2h[y] \le h[x] + h[y] - 2h[g]$? 如果 $g$ 是 LCA 的话，yes。

但为了简单，我们可以先接受标程方法：通过一边 DFS 记录后缀数组，对每个 $x$，找之前子树中深度满足 $2h[y] \le T[x] - h[x]$ 的最大值对应的 $dp[k-1][y]$。

---

4. 算法步骤总览

1. 初始化 $dp[0][v] = 2n$ 如果 $s_v=1$，否则 $-1$。
2. 对每个层次 $k = 1$ 到 $\log n$：
   • 对每个节点 $v$ 设置 $T[v] = dp[k-1][v]$（路径最大长度）。
   • 以 $T$ 数组为权值，跑重心分解，用 DFS 分阶段更新 $dp[k][v]$：
     • 在重心 $g$ 处，对每个子树 DFS，记录每个节点 $x$ 的 $h[x]$ 和 $tag[x]$。
     • 对某个 $x$，找之前子树里满足 $2h[y] \le T[x] - h[x]$ 的 $y$ 中，$dp[k-1][y]$ 最大。
     • 用后缀数组维护这个“最大值”。
   • 重复直到 $dp[k][v] \le 1$ 对大部分 $v$。
3. 最后输出：对每个 $v$，找最大的 $lev$ 使 $dp[lev][v] \ge 1$，输出 $lev+1$，否则 $-1$。

---

5. 复杂度

重心分解：$O(n \log n)$
每层跑 DFS：$O(n)$
层数 $O(\log n)$
总复杂度 $O(n \log^2 n)$，$n \le 7\times 10^4$ 可接受。

---

6. 结论

标程通过多阶段 DP + 重心分解，将条件 $2d_{i} \le d_{i+1}$ 转化为： 在重心 $g$ 处，对节点 $x$，要找到之前子树的一个节点 $y$，满足 $2h[y] \le T[x] - h[x]$，且 $dp[k-1][y]$ 最大，这样 $dp[k][x] = \max(dp[k][x], dp[k-1][y] + 1)$ 带某种约束。

最终输出每个点的最大可走步数 $lev+1$。

---

7. 示例验证

以第一个样例 $n=5$ 链 $1-2-3-4-5$，$s = 01111$ 为例，选的点是 2,3,4,5。

从 2 出发： 3(1) → 4(1) → 5(1) 路径 2-3-4-5 长度 3（边权 1,1,1）不满足 double。
但 2→4(2) 不行，因为第一次边权 1，第二次要≥2，可能 2→4(2) 然后 4→5(1)<2×无。
实际上最长 nice 路径 = 3 个点（样例输出 3），符合。