题解：「ROI 2023 Day2 T1」Улитка на склоне（基于提供代码）

核心思路总览

本题通过 树形DP预处理 + 直接查询 求解，核心是提前计算每个节点子树内满足“转弯次数≤k”的叶子节点数，查询时直接返回目标节点的预处理结果。整体复杂度为 $O(n + q)$，适配 $2 \times 10^5$ 规模的数据。

关键预处理

1. 树结构存储

• fa[u]：节点 $u$ 的父节点。
• son[u][0/1]：节点 $u$ 的左（0）、右（1）子节点（非叶子节点才有两个子节点）。
• type[u]：节点 $u$ 相对于父节点的方向（0=左子节点，1=右子节点；根节点 type 设为 -1 作为特殊标记）。

2. 树形DP核心状态

• cnt[u]：从根节点到节点 $u$ 的路径中，蜗牛的转弯次数。
• sum[u]：以 $u$ 为根的子树中，满足“从根节点到叶子节点的转弯次数≤k”的叶子节点总数（即查询 $u$ 时的答案）。

3. DP状态转移

（1）转弯次数 cnt[u] 计算

• 根节点（1）的 cnt[1] = 0（无前置方向，未转弯）。
• 对于非根节点 $u$：其父亲为 $fa[u]$，父亲的方向为 type[fa[u]]，$u$ 相对于父亲的方向为 type[u]。
• 若父亲的方向与 $u$ 的方向不同（根节点父亲方向为 -1，无对比），则转弯次数 +1，即 cnt[u] = cnt[fa[u]] + (type[fa[u]] != type[u])。

（2）子树有效叶子数 sum[u] 计算

• 若 $u$ 是叶子节点（son[u][0] == 0）：若 cnt[u] ≤ k，则 $u$ 是有效叶子，sum[u] = 1；否则 sum[u] = 0。
• 若 $u$ 是非叶子节点：子树有效叶子数 = 左子树有效叶子数 + 右子树有效叶子数，即 sum[u] = sum[son[u][0]] + sum[son[u][1]]。

代码解析

1. 输入处理与树结构构建

• 读取 $n, k, q$ 后，遍历每个节点：
  • 若 $t_i=2$（非叶子节点），读取左、右子节点，记录 son[i][0] 和 son[i][1]，并设置子节点的 fa 和 type。
  • 若 $t_i=0$（叶子节点），无需额外处理（son 数组默认初始化为 0）。

2. 深度优先搜索（DFS）遍历

• 从根节点（1）开始递归遍历整棵树：
  • 递归左、右子节点，计算其 cnt 和 sum。
  • 回溯时汇总非叶子节点的 sum（左+右子树之和）。

3. 查询处理

• 对于每个查询节点 $u_i$，直接输出 sum[u_i]，即 $u_i$ 子树内满足条件的叶子节点数。

关键验证（结合样例）

样例中 $k=1$，树结构如下：

• 根节点 1 的左子节点 2（叶子）、右子节点 4。
• 节点 4 的左子节点 3、右子节点 7（叶子）。
• 节点 3 的左子节点 6（叶子）、右子节点 5（叶子）。

各节点 cnt 计算：

• cnt[1] = 0，cnt[2] = 0（根→2 方向 0，无转弯）。
• cnt[4] = 0（根→4 方向 1，无转弯）。
• cnt[3] = 0 + (1 != 0) = 1（4→3 方向 0，与父方向 1 不同，转弯+1）。
• cnt[7] = 0 + (1 == 1) = 0（4→7 方向 1，与父方向 1 相同，无转弯）。
• cnt[6] = 1 + (0 == 0) = 1（3→6 方向 0，与父方向 0 相同，无转弯）。
• cnt[5] = 1 + (0 != 1) = 2（3→5 方向 1，与父方向 0 不同，转弯+1）。

各节点 sum 计算：

• 叶子节点：sum[2] = 1（cnt=0≤1），sum[7]=1（cnt=0≤1），sum[6]=1（cnt=1≤1），sum[5]=0（cnt=2>1）。
• 非叶子节点：sum[3] = 1+0=1，sum[4] = 1+1=2，sum[1] = 1+2=3。

查询结果：

• 查询 1→sum[1]=3，查询 4→sum[4]=2，查询 3→sum[3]=1，查询 5→sum[5]=0，与样例输出完全一致。

复杂度分析

• 时间复杂度：$O(n + q)$。DFS 遍历树耗时 $O(n)$，每个查询耗时 $O(1)$。
• 空间复杂度：$O(n)$。存储树结构、cnt、sum 数组的空间均为 $O(n)$，递归栈深度最坏为 $O(n)$（树退化为链），但题目中是悬挂二叉树（非叶子节点必有两个子节点），栈深度为 $O(\log n)$ 到 $O(n)$，可通过迭代 DFS 优化栈溢出风险。

关键结论

本题的核心是利用树形DP提前统计每个节点子树内的有效叶子数，将查询转化为直接查表。核心逻辑是准确计算“根到节点的转弯次数”，并基于此筛选有效叶子，最终实现高效查询。