题目解析：王室联邦（树分块问题）

本题要求将一棵树划分为若干个省（块），每个省的大小需在区间 [B, 3B] 内，且满足特定条件：每个省有一个省会（可位于省外），但省內任意城市到省会的路径上的所有城市（除省会外）必须属于该省。这本质上是一个树分块问题，需要通过合理的划分满足国王的管理需求。

算法核心思想

该问题的标准解法采用深度优先搜索（DFS）结合栈的贪心策略。关键思路如下： • DFS遍历树：从根节点（如节点1）开始DFS，维护一个栈记录访问顺序。

• 子树分块：在回溯过程中，若当前节点的某棵子树大小达到 B，则立即将这些节点划分为一个省（块），并以当前节点作为该省的省会。

• 剩余节点处理：DFS结束后，栈中剩余的节点（少于 B 个）并入最后一个省，确保最终所有节点被覆盖且块大小不超过 3B。

此方法能保证块大小在 [B, 3B] 内，且满足路径条件，因为省会设在了当前节点（子树根），路径上的节点均通过DFS连续分配。

算法步骤详解

1. 输入与初始化： • 读取城市数 N 和块大小下限 B。

   • 构建树的邻接表（无向图）。

2. DFS遍历与分块： • 栈维护：DFS进入节点 u 时，记录当前栈顶位置 now。

   • 子树处理：递归处理 u 的所有子节点。回溯时，检查栈中新增节点数（即 top - now）：

   ◦ 若 \geq B，则创建一个新省（块编号递增），将栈顶到 now 的节点弹出并分配到此省，省会设为 u。

   • 当前节点入栈：处理完所有子节点后，将 u 压入栈。

3. 处理剩余节点： • DFS完成后，若栈中还有未分配节点（数量必小于 B），全部归入最后一个省。由于之前每个块大小在 [B, 2B] 之间，加入剩余节点后最后一个块大小不超过 3B。

4. 输出结果： • 第一行输出省的数量 K。

   • 第二行输出每个城市所属的省编号。

   • 第三行输出每个省的省会城市编号。

正确性分析

• 块大小保证：每次分块时，子树大小至少为 B，但不超过 2B（因为DFS回溯时连续弹出）。剩余节点并入后，最后一个块大小不超过 3B。

• 路径条件满足：省会设为当前节点 u，由于分块基于DFS的子树连续性，从任意城市到 u 的路径上的节点均属于同一省。

• 时间复杂度：DFS遍历每个节点一次，复杂度 (O(N))，适用于 N \leq 1000 的约束。

关键点说明

• 省会可设在省外：算法中将省会设为当前节点 u，但 u 可能不属于该省（如分块后 u 未被弹出）。这仍满足条件，因为路径上的节点均属同一省。

• 多种方案可行性：该贪心策略是标准解法，能输出任意一种可行方案，无需考虑最优省数量。

此方法高效且简洁，确保了在树结构上合理分块，符合题目所有约束条件。