题解：知识点难度分配验证

问题分析

我们有一棵以 $1$ 为根的有根树，每个节点有一个难度值（可能已确定，可能未确定）。

规则：

• 对于有子节点的节点 $x$，设 $\max_x$ 是 $x$ 的所有子节点难度的最大值
• 如果恰好有一个子节点难度等于 $\max_x$，则 $x$ 的难度必须是 $\max_x$
• 否则（有多个子节点难度等于 $\max_x$ 或没有子节点难度等于 $\max_x$），则 $x$ 的难度必须是 $\max_x + 1$

叶子节点没有额外限制。

我们需要判断是否存在给未确定节点赋非负整数值的方式，使得所有节点满足上述规则。

---

关键观察

1. 规则理解

设节点 $x$ 有 $k$ 个子节点，子节点难度最大值为 $m$，$cnt$ 表示难度等于 $m$ 的子节点数量：

• 如果 $cnt = 1$：$x$ 的难度必须为 $m$
• 如果 $cnt \neq 1$：$x$ 的难度必须为 $m + 1$

2. 树形约束

约束从叶子向根传递。我们可以用 DFS 从叶子向上处理，检查约束是否一致。

---

算法设计

方法：DFS 后序遍历

从叶子节点开始向上处理，对于每个节点 $u$：

1. 如果 $u$ 是叶子：

   • 如果 $a[u]$ 已确定，直接使用
   • 如果未确定，暂时标记为"任意"（但需要非负整数）

2. 如果 $u$ 有子节点：

   • 先递归处理所有子节点
   • 从子节点获取信息：最大难度 $max\_child$，达到最大难度的子节点数量 $cnt\_max$
   • 根据规则计算 $u$ 的理论难度 $expected$
   • 检查是否与已确定的 $a[u]$ 冲突

3. 信息表示

由于未确定的节点可以灵活赋值，我们需要表示一个节点的可能难度范围：

• 如果节点难度已确定，就是固定值
• 如果未确定，我们需要知道它必须满足的约束

但实际上，我们可以用"必须等于某个值"或"必须大于等于某个值"来表示。

---

具体实现思路

定义 DFS 返回一个三元组 $(low, high, fixed)$：

• $low$：该节点难度的下界
• $high$：该节点难度的上界（如果固定）
• $fixed$：是否必须为固定值

DFS(u) 过程：

1. 如果 $u$ 是叶子：

   • 如果 $a[u]$ 已确定：返回 $(a[u], a[u], \text{true})$
   • 否则：返回 $(0, \infty, \text{false})$（可以是任意非负整数）

2. 否则：

   • 递归处理所有子节点，得到每个子节点的 $(low_i, high_i, fixed_i)$
   • 计算 $m = \max(low_i)$（子节点难度的最大下界）
   • 统计有多少子节点的区间包含 $m$ 且可能是唯一最大值
   • 根据规则推导 $u$ 的约束

实际上更简单的方法是：DFS 返回该节点必须满足的难度值（如果可确定）或返回需要的信息让父节点判断。

---

更简洁的方法

我们只需要检查从叶子到根的约束是否一致。

对于节点 $u$：

• 如果 $a[u]$ 已确定，记 $val = a[u]$
• 如果未确定，记 $val = -1$

DFS 返回该节点在满足约束的情况下，子节点需要的最大难度（即 $\max_x$）以及可行性。

算法步骤：

1. DFS(u):

   • 如果 $u$ 是叶子：
     • 如果 $val \neq -1$，返回 $(val, \text{true})$
     • 否则返回 $(0, \text{true})$（叶子可以设为0）

2. 否则：

   • 递归处理所有子节点，得到每个子节点的难度 $d_v$（已确定或计算出的）
   • 计算 $m = \max(d_v)$
   • 统计 $cnt = \text{满足 } d_v = m \text{ 的子节点数}$
   • 如果 $val \neq -1$（$u$ 难度已确定）：
     • 检查是否满足规则：如果 $cnt = 1$ 则 $val$ 必须等于 $m$，否则 $val$ 必须等于 $m+1$
     • 如果不满足，返回 $(0, \text{false})$
   • 如果 $val = -1$（$u$ 难度未确定）：
     • 根据规则自动确定 $u$ 的难度：如果 $cnt = 1$ 则 $u$ 难度为 $m$，否则为 $m+1$
   • 返回 $(u\text{的难度}, \text{true})$

---

验证样例

样例1（合理）：

3
0 -1 0
1 2
2 3

树：1 → 2 → 3

• 节点3（叶子）：难度0
• 节点2：子节点最大难度0，唯一最大值 → 节点2难度应为0
• 节点1：子节点最大难度0，唯一最大值 → 节点1难度应为0 与给定的节点1难度0一致，合理。

样例2（不合理）：

3
0 -1 0  
1 2
1 3

树：1 → 2, 1 → 3

• 节点2：未定（可设为任意值）
• 节点3：难度0
• 节点1：子节点最大难度 = max(?, 0)
  • 如果设节点2难度为0，则 $cnt=2$，节点1难度应为1，与给定的0冲突
  • 如果设节点2难度>0，则 $cnt=1$，节点1难度应为节点2难度，与给定的0冲突 无论如何都矛盾。

---

复杂度分析

• 时间复杂度：$O(n)$，每个节点处理一次
• 空间复杂度：$O(n)$，存储树结构和DFS栈

在 $n \le 10^5$ 且 $\sum n \le 2\times 10^5$ 时完全可行。

---

代码框架

#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> children;
vector<int> a;

// 返回 (该节点难度, 是否可行)
pair<int, bool> dfs(int u) {
    if (children[u].empty()) {
        // 叶子节点
        if (a[u] != -1) return {a[u], true};
        else return {0, true};  // 未确定的叶子可设为0
    }
    
    int max_child = -1;
    for (int v : children[u]) {
        auto [val, ok] = dfs(v);
        if (!ok) return {0, false};
        max_child = max(max_child, val);
    }
    
    // 统计达到最大值的子节点数
    int cnt_max = 0;
    for (int v : children[u]) {
        auto [val, ok] = dfs(v);  // 这里可以优化，避免重复计算
        if (val == max_child) cnt_max++;
    }
    
    if (a[u] != -1) {
        // 难度已确定，检查是否满足规则
        if (cnt_max == 1) {
            if (a[u] != max_child) return {0, false};
        } else {
            if (a[u] != max_child + 1) return {0, false};
        }
        return {a[u], true};
    } else {
        // 难度未确定，根据规则确定
        if (cnt_max == 1) {
            return {max_child, true};
        } else {
            return {max_child + 1, true};
        }
    }
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        a.resize(n+1);
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        
        children.assign(n+1, vector<int>());
        for (int i = 0; i < n-1; i++) {
            int u, v;
            cin >> u >> v;
            children[u].push_back(v);  // u依赖v，即u是v的父节点
        }
        
        auto [val, ok] = dfs(1);
        if (ok) cout << "Reasonable" << endl;
        else cout << "Unreasonable" << endl;
    }
    return 0;
}

---

总结

本题的关键在于：

1. 理解树形依赖规则
2. 设计从叶子到根的DFS验证算法
3. 处理已确定和未确定节点的不同情况
4. 检查规则约束的一致性

这是一个典型的树形结构+约束验证问题，考察对树遍历和规则处理的能力。