一、问题理解

我们有一棵有根树，根深度为 $1$，叶子节点初始权值为编号 $i$，非叶子节点的权值由规则确定：

• 深度为奇数：权值 = 子节点权值 $\max$
• 深度为偶数：权值 = 子节点权值 $\min$

这样得到根节点权值 $W$。

Cedyks 可以控制叶子节点集合 $S$，修改它们的权值（任意整数），花费的能量为：

$$\max_{i \in S} |i - w_i|$$

目标：让根节点权值 改变 的最小能量 = $w(S)$。如果不可能改变，则 $w(S) = n$。

我们要统计对于 $k \in [L, R]$，有多少个 $S$ 满足 $w(S) = k$。

---

二、关键观察

1. 原树根权值 $W$ 的意义

初始时叶子权值就是编号，所以整棵树是一个 静态 Minimax 博弈树，$W$ 是根的值。

2. 改变根权值的条件

假设我们只能改 $S$ 中的叶子。对于树上的每个节点 $u$，定义：

• 如果 $u$ 是叶子：它的权值要么固定（不在 $S$ 中），要么可任意改（在 $S$ 中）。
• 如果 $u$ 是非叶子：
  • 深度奇数（取 $\max$）：要改变 $u$ 的权值，必须让某个子节点的值 大于当前值，且该子节点可改或它的子树可改。
  • 深度偶数（取 $\min$）：要改变 $u$ 的权值，必须让某个子节点的值 小于当前值，且该子节点可改或它的子树可改。

但这里 $w(S)$ 的定义是 最小能量 使得根值改变。

---

3. 等价转化

设原根权值 $W$。

对于叶子 $i$，如果我们把它改成 $W$，根值不一定改变，因为可能别的叶子值使得取 $\max$/$\min$ 时还是 $W$。

重要思路：
根值改变 ⇔ 存在一条从根到某个叶子的路径，路径上的每个节点的值都因为 $S$ 中的叶子的修改而可以越过某个阈值，使得根值不等于 $W$。

---

4. 对每个叶子定义“关键值”

定义 $low_i$ 和 $high_i$：

• 如果叶子 $i$ 的初始值 $i < W$，那么要让它所在的子树输出值影响父节点（深度奇偶考虑），需要把它提升到至少 $W+1$（对于 max 节点）或降低到 $W-1$（对于 min 节点）？ 这里要小心。

实际上，更系统的做法是 从根向下推关键区间：

设 $[L_u, R_u]$ 表示：要使节点 $u$ 的值 不等于 它当前的值 $val_u$，它的新值必须落在区间 $[L_u, R_u]$ 之外（即 $< L_u$ 或 $> R_u$）吗？
不对，更准确地说：我们想改变 $u$ 的值，那么它的新值必须 不等于 $val_u$。但是它的父节点对它的要求取决于父节点类型。

---

标准框架（已知技巧）：

定义 $need_u$ 为：为了改变根的值，$u$ 的权值必须 大于 还是 小于 某个阈值？

• 根节点：要改变根值，新值 $x \neq W$。
• 如果 $u$ 是 max 节点（深度奇数），当前值 $val_u$，那么要改变它，必须让某个孩子的值 $> val_u$（因为 max 节点值 = 孩子最大值，要改变必须有一个孩子大于当前值）。
• 如果 $u$ 是 min 节点（深度偶数），要改变它，必须让某个孩子的值 $< val_u$。

从根向下传播条件：

• 根：$change(root) = true$，阈值类型？ 其实我们关心的是：从根到叶的路径上，每个节点要改变，需要它的某个孩子满足什么条件。

---

更常见的做法是定义 关键值 $b_i$ 对每个叶子 $i$：

从根向下推：

• 根：要改变，需要某个子节点值 $> W$（若深度=1奇数）或 $< W$（若深度=1奇数？这里深度1是奇数，所以是 max 节点，所以需要某个孩子值 $> W$）。

实际上，我们定义 $threshold(u)$：节点 $u$ 要改变父节点的值，它需要满足的值条件。

设 $p$ 是 $u$ 的父节点，$val_p$ 是 $p$ 的原值。

• 若 $p$ 是 max 节点：$p$ 的值 = 孩子最大值。要改变 $p$ 的值，必须有某个孩子 $v$ 的值 $> val_p$。如果 $u$ 是那个孩子，则 $u$ 的新值必须 $> val_p$；如果 $u$ 不是那个孩子，则 $u$ 不需要改变，别的孩子改变即可。
• 但我们要的是 通过 u 改变 p 的条件：$u$ 的新值 $> val_p$，并且 $u$ 必须是能大于 $val_p$ 的那个孩子（即 $u$ 的原值可能是 $val_p$ 或更小，但我们可以改大它）。

所以对每个节点 $u$，定义 $bound(u)$ = 如果要让根改变，$u$ 需要达到的值（上界或下界）。

---

推演：

1. 根：$bound(root) = (W, +\infty)$ 表示需要 $> W$（因为深度1奇数，max节点，要改变必须大于原值）。
2. 对节点 $u$，设 $bound(u) = (t, \infty)$ 表示需要 $> t$，或 $(0, t)$ 表示需要 $< t$（0是假想的极小值，其实用 $-\infty$ 更合适，但这里用 $t$ 表示阈值，方向表示大于还是小于）。

• 若 $u$ 是 max 节点，$bound(u) = (t, \infty)$：
  要改变 $u$，需要某个孩子 $v$ 的值 $> val_u$。
  但 $u$ 要满足父节点的条件 $bound(p)$，所以 $u$ 的新值必须满足 $bound(p)$。
  所以 $u$ 的新值必须 $> t_p$（若 $bound(p) = (t_p, \infty)$）且 $u$ 的新值 $> val_u$ 才能改变自己。
  所以对 $v$：$bound(v) = (\max(t_p, val_u), \infty)$。

• 若 $u$ 是 min 节点，$bound(u) = (0, t)$（表示 $< t$）：
  要改变 $u$，需要某个孩子 $v$ 的值 $< val_u$。
  同时 $u$ 的新值必须满足 $bound(p)$：若 $bound(p) = (0, t_p)$，则 $u$ 的新值必须 $< t_p$ 且 $u$ 的新值 $< val_u$ 才能改变自己。
  所以对 $v$：$bound(v) = (0, \min(t_p, val_u))$。

---

这样我们可以 DFS 算出每个叶子的 $bound$：$(low, high)$ 形式，表示叶子需要 $> low$ 或 $< high$ 来影响根值。

实际上最终 $bound$ 会变成单边条件：要么需要 $> X$，要么需要 $< X$。

---

5. 叶子的关键值 $b_i$

定义 $b_i$ = 叶子 $i$ 要参与改变根值，必须改变到的 最小绝对值偏移。

• 如果需要 $> X$，则必须 $w_i \ge X+1$，最小偏移 = $\max(0, X+1 - i)$（如果 $i \le X$）。
• 如果需要 $< X$，则必须 $w_i \le X-1$，最小偏移 = $\max(0, i - (X-1))$（如果 $i \ge X$）。

如果 $i$ 已经满足条件（比如需要 $> X$ 且 $i > X$），则不用改，偏移 0。

---

6. 集合 $S$ 的稳定度

如果 $S$ 中所有叶子的 $b_i$ 都无穷大（无法改变根），则 $w(S) = n$。

否则，$w(S) = \max_{i \in S} b_i$？ 不对，因为我们可以同时改多个叶子，取所需最大的 $b_i$ 作为花费。

更准确：
$w(S)$ = 最小的 $d$ 使得存在一种改法，花费 $d$，让根改变。
花费 $d$ 表示每个 $i \in S$ 可以改成 $[i-d, i+d]$ 内任意值。

根能改变 ⇔ 存在叶子 $i \in S$ 使得 $b_i \le d$？ 不，因为可能需多个叶子同时改才能改变路径上所有节点。

实际上，对每个叶子 $i$，定义 $d_i = b_i$ 为它单独改变所需最小花费。
但整条路径上可能需要多个叶子合作：$w(S)$ = 所有从根到叶的路径中，路径上所有在 $S$ 中的叶子的 $d_i$ 的 最大值 的最小值？ 这比较复杂。

---

已知结论（这类题的套路）：
$w(S) = \min\{ \max_{i \in P \cap S} d_i \}$ over 所有根到叶的路径 $P$。

因为要改变根，必须改变某条路径上的每个节点，每个节点改变需要某个孩子的值越过阈值，这对应路径上某个叶子的 $d_i$。整条路径的瓶颈是最大的 $d_i$（$i \in S$）。我们要选路径使这个瓶颈最小。

所以：

$$w(S) = \min_{\text{路径 } P} \max_{i \in P \cap S} d_i $$

如果某路径 $P$ 与 $S$ 不交，则 $\max$ 取 $\infty$。

---

7. 转化为：对每个 $k$，数多少 $S$ 满足 $\min_P \max_{i \in P \cap S} d_i = k$。

设 $m$ = 叶子数。

先求 $d_i$ 数组（通过 DFS 传播阈值计算）。

---

8. 计数方法

令 $f(k)$ = 满足 $w(S) \le k$ 的 $S$ 个数。
则 $ans(k) = f(k) - f(k-1)$ 对于 $k < n$，且 $ans(n) = 2^m - 1 - f(n-1)$。

$w(S) \le k$ ⇔ 每条路径 $P$ 上存在 $i \in S$ 使得 $d_i \le k$（否则有条路径全不在 $S$ 或 $d_i > k$，则瓶颈 $> k$）。

即：$S$ 必须 覆盖 所有 $d_i > k$ 的叶子（即这些叶子必须在 $S$ 中？不对，仔细想：如果某路径上所有叶子的 $d_i > k$，则这条路径的瓶颈 $> k$，所以 $w(S) > k$。所以要 $w(S) \le k$，必须每条路径上至少有一个叶子 $d_i \le k$）。

所以：$w(S) \le k$ ⇔ 所有叶子集合 $\{i: d_i > k\}$ 不包含任何一条完整路径？ 更准确：$\{i: d_i \le k\}$ 必须是一个 路径覆盖 的击中集（即每条路径至少有一个 $d_i \le k$ 的叶子）。

---

所以计数：$T = \{i: d_i \le k\}$，要数 $S$ 满足 $S \cap T \neq \emptyset$ 对于每条路径 $P$？ 不对，是 $S$ 必须包含每个路径 $P$ 中至少一个 $i \in T$？ 不，$S$ 只要与 $T$ 在每条路径有交即可。

即：$T$ 是“可用叶子”，$S$ 必须满足：$S \cap T$ 是路径覆盖的击中集。

但 $S$ 可以包含 $T$ 以外的点，不影响。

---

更简单：定义 $A$ = $\{i: d_i \le k\}$，$B$ = 补集。
$w(S) \le k$ ⇔ 每条路径至少包含一个 $A$ 中的叶子 且在 $S$ 中？ 不对，在 $S$ 中才可改。
所以条件：每条路径 $P$ 满足 $P \cap S \cap A \neq \emptyset$。

即 $S \cap A$ 是路径覆盖的击中集。

---

9. 路径覆盖的计数

树的所有根到叶路径，要击中至少一个在 $S \cap A$ 中。

等价于：$S$ 必须包含 $A$ 的一个 路径覆盖集（即 $S \cap A$ 包含一个路径覆盖）。

最小路径覆盖？ 在树上，所有路径的击中集 = 包含所有叶子的某个祖先集合。其实树上根到叶路径的击中集 = 包含所有叶子的某个 前缀（在 DFS 序上）？ 不对。

其实：树上根到叶路径族的最小击中集 = 所有叶子（因为每个叶子是一条路径的终点，必须击中它自己）。
但这里路径是根到叶，所以击中集必须包含每个叶子？ 不对，因为一条路径可能被击中在中间节点（如果中间节点是叶子？不可能，中间节点不是叶子）。
所以必须包含每个叶子？ 是的：因为叶子 $l$ 是路径 $root \to l$ 的终点，要击中这条路径，必须击中该路径上的某个叶子（因为只有叶子在 $A$ 中才可能 $d_i \le k$），所以必须击中 $l$ 本身（如果 $l \in A$）或者路径上其他叶子（但路径上其他节点不是叶子，所以只有 $l$ 本身是叶子）。
所以：要击中路径 $P$（终点叶 $l$），必须 $l \in S \cap A$。

因此条件简化为：所有叶子 $l$ 如果 $d_l \le k$，则必须 $l \in S$？ 不对，如果 $d_l \le k$，不一定需要 $l \in S$，因为可能另一条路径通过别的叶子击中？ 但路径 $P_l$ 的终点是 $l$，要击中它，必须 $l \in S$ 且 $l \in A$？ 不，如果 $l \notin A$（$d_l > k$），则这条路径无法被 $A$ 中的叶子击中（因为路径上唯一叶子是 $l$），所以不可能满足条件。
所以：如果存在叶子 $l$ 满足 $d_l > k$，那么 $w(S) > k$。
所以 $w(S) \le k$ ⇔ 所有叶子 $l$ 满足 $d_l \le k$（即 $A$ 包含所有叶子）。

---

重要结论：
$w(S) \le k$ ⇔ $\max_{i} d_i \le k$（即所有叶子的 $d_i \le k$）。

那么 $w(S) = \min_P \max_{i \in P\cap S} d_i$，如果所有 $d_i \le k$，则显然 $w(S) \le k$。反过来，如果某个 $d_i > k$，取路径 $P$ 为根到 $i$，则 $P\cap S$ 包含 $i$（因为 $i$ 是叶子），所以 $\max \ge d_i > k$，所以 $w(S) > k$。

所以：

$$w(S) = \max_{i} d_i \quad\text{？不对，应该是 } w(S) = \max_{i \in S} d_i $$

因为 $w(S) = \min_P \max_{i \in P\cap S} d_i$，但 $P$ 是根到叶路径，$i$ 是路径的终点叶，所以 $P\cap S$ 要么空要么包含 $i$，所以 $\max_{i \in P\cap S} d_i = d_i$ 如果 $i \in S$，否则 $\infty$。
所以 $w(S) = \min_{i \in S} d_i$？ 不对，是 $\min_P$ 外面，对路径 $P$ 取 $\min$：
$w(S) = \min_{\text{叶子 } i \in S} d_i$？ 不对，应该是 $\min_{\text{叶子 } i} \{ \text{如果 } i \in S \text{ 则 } d_i \text{ 否则 } \infty \}$？ 即 $w(S) = \min_{i \in S} d_i$。

这更简单了！
因为每条路径 $P$ 的终点叶 $i$，如果 $i \in S$，则这条路径的瓶颈是 $d_i$，否则无穷大。我们要所有路径的最小瓶颈，所以就是所有 $i \in S$ 的 $d_i$ 的最小值。

所以：

$$w(S) = \min_{i \in S} d_i$$

如果 $S$ 中所有 $d_i$ 都 $> n$（不可能），则 $w(S) = n$。

---

10. 最终简化

$d_i$ 计算后，$w(S) = \min_{i \in S} d_i$，特殊地，如果 $\min_{i \in S} d_i$ 不存在（不可能）或 所有 $d_i > n$ 则 $w(S) = n$。

那么计数就简单了：

对 $k < n$：
$w(S) = k$ ⇔ $\min_{i \in S} d_i = k$ ⇔ $S$ 包含至少一个 $d_i = k$ 的叶子，且不包含任何 $d_i < k$ 的叶子，且所有 $d_i = k$ 的叶子不全在 $S$ 中？ 不对，$\min$ 正好 $k$ 表示：$S$ 中所有 $d_i \ge k$ 且至少一个 $d_i = k$。

所以：令 $cnt_a = \#\{i: d_i < k\}$， $cnt_b = \#\{i: d_i = k\}$， $cnt_c = \#\{i: d_i > k\}$。

$S$ 不能包含任何 $d_i < k$ 的叶子（否则 $\min$ 会更小），必须包含至少一个 $d_i = k$ 的叶子，$d_i > k$ 的叶子任意。

所以方案数 = $(2^{cnt_b} - 1) \times 2^{cnt_c}$。

对 $k = n$：
$w(S) = n$ ⇔ $S$ 中所有叶子 $d_i \ge n$（即 $S \subseteq \{i: d_i \ge n\}$）且非空。
如果所有 $d_i < n$，则不可能 $w(S)=n$。
所以方案数 = $2^{cnt_{\ge n}} - 1$，其中 $cnt_{\ge n} = \{i: d_i \ge n\}$。

---

11. 算法步骤

1. DFS 计算原树每个节点的权值 $val_u$。
2. DFS 从根传播 $bound$ 计算每个叶子的 $d_i$：
   • 根：$bound = (W, \infty)$ 表示需要 $> W$。
   • 对节点 $u$，若 $bound = (t, \infty)$（需要 $> t$）：
     • 若 $u$ 是 max 节点：要改变 $u$，需要某个孩子值 $> val_u$，同时 $u$ 的新值必须 $> t$，所以对每个孩子 $v$，$bound(v) = (\max(t, val_u), \infty)$。
     • 若 $u$ 是 min 节点：要改变 $u$，需要某个孩子值 $< val_u$，同时 $u$ 的新值必须 $> t$（这不可能，因为 min 节点值 $< val_u$ 才能改变，但 $u$ 的新值又要 $> t$，矛盾如果 $t \ge val_u$）。所以如果 $t \ge val_u$，则 $u$ 不可能改变父节点值，$bound(v) = \infty$。否则，$bound(v) = (-\infty, \min(val_u, \dots))$ 这里要仔细，但大致这样推。 实际实现时，可以统一用 $bound = [L, R]$ 表示新值必须在 $[L,R]$ 外才能改变根，然后推演。

但已知结论：最终 $d_i = |i - W|$ 对于大多数叶子？ 不对，样例中 $d_4 = 1$，$d_2 = 3$，$d_3=3$，$W=4$，$|2-4|=2$ 不是 3，所以不是简单绝对值。

这里推导略复杂，但思路如此。

---

12. 最终公式

设 $cnt[k] = \{i: d_i = k\}$。

对 $k < n$：

$$ans(k) = (2^{cnt[k]} - 1) \times 2^{\sum_{j>k} cnt[j]} $$

对 $k = n$：

$$ans(n) = 2^{\sum_{j\ge n} cnt[j]} - 1$$

其中 $d_i$ 通过 DFS 传播 $bound$ 得到。