{"problem":{"name":"[THUPC 2023 决赛] 大纲","description":{"content":"小 I、小 O 和小 N 是 ION 大纲的编写者，小 I 负责给每个知识点定难度。 ION 大纲计划列入 $n$ 个知识点，其中小 I 按照自己的认识给其中部分知识点定好了难度，还有部分知识点没有定难度。 知识点之间有依赖关系，这个依赖关系恰好构成了一棵以 $1$ 为根的外向树，知识点 $x$ 指向知识点 $y$ 表示 $x$ 依赖 $y$。**依赖关系不具有传递性。** 你需要告诉小 I","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9386"},"statements":[{"statement_type":"Markdown","content":"小 I、小 O 和小 N 是 ION 大纲的编写者，小 I 负责给每个知识点定难度。\n\nION 大纲计划列入 $n$ 个知识点，其中小 I 按照自己的认识给其中部分知识点定好了难度，还有部分知识点没有定难度。\n\n知识点之间有依赖关系，这个依赖关系恰好构成了一棵以 $1$ 为根的外向树，知识点 $x$ 指向知识点 $y$ 表示 $x$ 依赖 $y$。**依赖关系不具有传递性。**\n\n你需要告诉小 I 目前确定下来的难度是否合理。我们认为确定下来的难度是合理的当且仅当存在一个给所有未确定难度的知识点确定难度的方式，使得以下所有条件成立：\n\n- 每个知识点的难度都是非负整数；\n- 对于每个依赖其他知识点的知识点 $x$，设 $\\max_x$ 为 $x$ 依赖的知识点中难度的最大值，则如果 $x$ 恰依赖一个难度为 $\\max_x$ 的知识点，那么知识点 $x$ 的难度为 $\\max_x$，否则为 $\\max_x+1$。**对于不依赖其他知识点的知识点，没有其他限制。**\n\n## Input\n\n**本题有多组测试数据**。第一行一个整数 $T$ 表示测试数据组数，接下来依次读入每组测试数据。\n\n对于每组测试数据，\n\n- 第一行一个整数 $n$ 表示知识点数量。\n- 第二行 $n$ 个整数 $a_1,a_2,\\cdots,a_n$，描述每个知识点的难度。若 $a_i = -1$ 表示知识点 $i$ 未确定难度，否则知识点 $i$ 的难度确定为 $a_i$。\n- 接下来 $n-1$ 行每行两个整数 $u,v$，表示依赖关系构成的外向树中的一条有向边。\n\n## Output\n\n对于每组测试数据输出一行：若难度是合理的，输出 `Reasonable`，否则输出 `Unreasonable`。\n\n[samples]\n\n## Note\n\n### 样例 1 解释\n\n对于第一组测试数据，将知识点 $2$ 的难度定为 $0$ 即满足条件。\n\n对于第二组测试数据，无论如何指定知识点 $2$ 的难度，知识点 $1$ 的难度会产生矛盾。\n\n### 数据规模与约定\n\n对于所有测试数据，$1 \\le T \\le 10^5$，$2 \\le n \\le 10^5$，$-1 \\le a_i \\le 10^9$，$1 \\le u,v \\le n$。  \n保证单个测试点中所有测试数据的 $n$ 的和不超过 $2 \\times 10^5$，每组测试数据输入的所有边构成一棵以 $1$ 为根的外向树。\n\n### 后记\n\n大纲发表了。若干天后，小 I 给 ION 比赛投题，却发现有人偷偷改了一笔难度表，导致他的题目超纲。于是小 I 只能把题投给 CPUHT。\n\n### 题目来源\n\n来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。\n\n题解等资源可在 <https://github.com/THUSAAC/THUPC2023> 查看。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9386","tags":["2023","O2优化","树形 DP","THUPC"],"sample_group":[["2\n3\n0 -1 0\n1 2\n2 3\n3\n0 -1 0\n1 2\n1 3\n","Reasonable\nUnreasonable\n"]],"created_at":"2026-03-03 11:09:25"}}