题解：树上选点方案计数问题

题目分析

本题要求在一棵以1为根的树上选择满足以下条件的点集，计算方案总数：

1. 若选择某个节点，则必须选择其父亲节点（选点集是“祖先-后代连通”的）；
2. 所选点的权值互不重复；
3. 对于每个选中的节点，其子树中所有选中点的权值构成公差为1的等差数列。

核心思路

关键在于理解“子树权值构成公差为1的等差数列”这一条件。该条件意味着：对于任意选中的节点x，其所有子树中被选中的权值必须形成一个包含v[x]的连续区间（如[a, b]，其中a ≤ v[x] ≤ b，且区间内所有整数均出现）。

基于此，我们可以通过自底向上的DFS，为每个节点维护两个集合：

• L[x]：记录以x为根的子树中，若x被选中，可能的最小权值（即连续区间的左边界）；
• R[x]：记录以x为根的子树中，若x被选中，可能的最大权值（即连续区间的右边界）。

通过合并子节点的L和R信息，最终根节点的L和R集合可直接用于计算总方案数。

详细步骤

1. 初始状态
   对于单个节点x（无选中子节点时），唯一合法方案是仅选x本身，因此L[x] = {v[x]}，R[x] = {v[x]}。

2. 子树信息合并
   处理节点x时，需先递归处理其所有子节点，再按以下规则合并子节点的信息：

   • 对于子节点y，若v[y] > v[x]：
     要将y的子树纳入x的子树方案，y的子树最小权值必须为v[x] + 1（才能与v[x]形成连续区间）。若满足，则x的最大权值集合R[x]可合并y的最大权值集合R[y]（即R[x] = R[x] ∪ R[y]）。
   • 对于子节点y，若v[y] < v[x]：
     要将y的子树纳入x的子树方案，y的子树最大权值必须为v[x] - 1（才能与v[x]形成连续区间）。若满足，则x的最小权值集合L[x]可合并y的最小权值集合L[y]（即L[x] = L[x] ∪ L[y]）。

   合并时需按子节点权值排序，确保处理顺序不影响结果（先处理权值小的子节点还是大的子节点，需根据合并方向调整）。

3. 结果计算
   根节点（1号节点）的L[1]记录了所有可能的区间左边界，R[1]记录了所有可能的区间右边界。每个左边界a ∈ L[1]和右边界b ∈ R[1]（满足a ≤ v[1] ≤ b）对应一个唯一的合法方案（即权值为a, a+1, ..., b的点集）。因此，总方案数为L[1]的大小与R[1]的大小的乘积。

关键观察

• 权值唯一性由“连续区间”条件自然保证：若存在重复权值，区间无法连续（公差为1的等差数列中所有元素唯一）。
• 父节点必选的条件通过DFS的“自底向上”处理保证：子节点的信息仅在父节点被选中时才会被合并。

算法标签

• 树的深度优先搜索（DFS）
• 动态规划（子树信息合并）
• 集合运算（维护区间边界）