在预处理父数组时，fa[u][k] 表示节点 u 的第 2 k 2 k 级祖先。具体来说：

定义：fa[u][k] 是节点 u 向上跳 2 k 2 k 步后到达的祖先节点。

递推关系：预处理时通过动态规划计算，递推公式为：

fa [ u ] [ k ]

fa [ fa [ u ] [ k − 1 ]

] [ k − 1 ] fa[u][k]=fa[ fa[u][k−1] ][k−1] 即节点 u 的第 2 k 2 k 级祖先等于其第 2 k − 1 2 k−1 级祖先的第 2 k − 1 2 k−1 级祖先。

边界条件：fa[u][0] 是 u 的直接父节点（一步祖先）。

应用：这种倍增方法常用于高效求解 最近公共祖先（LCA） 或快速定位节点的远祖，将查询时间复杂度优化至 O ( log ⁡ n ) O(logn)。

例如，fa[u][1] 是 u 的祖父节点，fa[u][2] 是 u 的曾祖父节点，依此类推。预处理时需计算 k max ⁡

⌊ log ⁡ 2 ( 树深度 ) ⌋ k max ​ =⌊log 2 ​ (树深度)⌋，确保覆盖树的最大可能深度。