题目理解

这是一道树形结构+贪心推理的题目，题意可以概括为：

• 有一棵 $n$ 个节点的有根树
• 每个节点有一个 $1$ 到 $n$ 的唯一权值
• 权值满足：父节点的权值大于所有子节点的权值
• 部分节点的权值已知，已知权值的节点的父节点权值也已知
• 要求推断出所有可以唯一确定的未知权值

算法思路

核心观察

1. 权值分布特性：由于父节点权值大于子节点，整棵树从根到叶子权值递减
2. 已知权值形成链：已知权值的节点与其父节点形成一条递减链
3. 可用权值区间：对于每个"已知权值区间"，可以分配给该子树下的未知节点

关键数据结构

• sure[i]：节点 $i$ 的权值（已知或推导出的）
• used[i]：标记权值 $i$ 是否已被使用
• lst[i]：记录小于等于 $i$ 的最大未使用权值
• mxx[i]：记录最大权值为 $i$ 的子树中的节点数量
• pt_mx_val[i]：存储最大权值为 $i$ 的子树中的节点

算法步骤

1. 预处理未使用权值链

   for (int i = 1; i <= n; i++) {
       if (used[i])
           lst[i + 1] = lst[i];  // 延续前一个未使用值
       else
           lst[i + 1] = i;       // 当前值未使用
   }
   

   建立了一个"未使用权值"的链表，可以快速找到可用的权值。

2. 第一次DFS统计节点数量

   • 遍历整棵树，统计每个"最大可用权值"对应的节点数量
   • 如果遇到已知权值的节点，就更新当前的最大可用权值

3. 第二次DFS收集具体节点

   • 再次遍历，这次记录每个权值区间对应的具体节点

4. 贪心分配权值

   for (int i = 1; i <= n; i++) {
       cntval++;  // 可用权值计数
       for (auto x : pt_mx_val[i]) {
           cntpt++;  // 需要分配权值的节点计数
       }
       
       // 关键条件：如果只有一个权值和一个节点，就唯一确定
       if (cntval == 1 && cntpt == 1) {
           sure[pt_mx_val[i][0]] = i;
       }
       
       // 重置计数器
       if (cntval == cntpt)
           cntval = cntpt = 0;
   }
   

算法正确性分析

该算法的核心在于：

• 利用父节点权值大于子节点的性质，将树划分为多个权值区间
• 对于每个区间，如果可用权值数量与节点数量匹配，就可以唯一确定分配
• 特别地，当某个区间只有一个权值和一个节点时，这个节点的权值就被唯一确定了

时间复杂度

• 两次DFS：$O(n)$
• 权值分配：$O(n)$
• 总体复杂度：$O(n)$，适合 $n \leq 10^6$ 的数据范围

样例分析

对于题目样例：

输入：
10
2 2
2 10  
1 0
2 9
2 5
4 0
6 0
6 0
5 0
5 0

输出：
2
10
1
9
5
8
0
0
0
0

算法成功推断出：

• 节点6的权值为8（唯一可能）
• 其他未知节点无法唯一确定，输出0

这个解法巧妙地利用了树形结构的权值约束条件，通过统计和匹配来完成权值推断。