P9386 [THUPC 2023 决赛] 大纲题目描述小 I、小 O 和小 N 是 ION 大纲的编写者小 I 负责给每个知识点定难度。ION 大纲计划列入n nn个知识点其中小 I 按照自己的认识给其中部分知识点定好了难度还有部分知识点没有定难度。知识点之间有依赖关系这个依赖关系恰好构成了一棵以1 11为根的外向树知识点x xx指向知识点y yy表示x xx依赖y yy。依赖关系不具有传递性。你需要告诉小 I 目前确定下来的难度是否合理。我们认为确定下来的难度是合理的当且仅当存在一个给所有未确定难度的知识点确定难度的方式使得以下所有条件成立每个知识点的难度都是非负整数对于每个依赖其他知识点的知识点x xx设max ⁡ x \max_xmaxx​为x xx依赖的知识点中难度的最大值则如果x xx恰依赖一个难度为max ⁡ x \max_xmaxx​的知识点那么知识点x xx的难度为max ⁡ x \max_xmaxx​否则为max ⁡ x 1 \max_x1maxx​1。对于不依赖其他知识点的知识点没有其他限制。输入格式本题有多组测试数据。第一行一个整数T TT表示测试数据组数接下来依次读入每组测试数据。对于每组测试数据第一行一个整数n nn表示知识点数量。第二行n nn个整数a 1 , a 2 , ⋯ , a n a_1,a_2,\cdots,a_na1​,a2​,⋯,an​描述每个知识点的难度。若a i − 1 a_i -1ai​−1表示知识点i ii未确定难度否则知识点i ii的难度确定为a i a_iai​。接下来n − 1 n-1n−1行每行两个整数u , v u,vu,v表示依赖关系构成的外向树中的一条有向边。输出格式对于每组测试数据输出一行若难度是合理的输出Reasonable否则输出Unreasonable。输入输出样例 #1输入 #12 3 0 -1 0 1 2 2 3 3 0 -1 0 1 2 1 3输出 #1Reasonable Unreasonable说明/提示样例 1 解释对于第一组测试数据将知识点2 22的难度定为0 00即满足条件。对于第二组测试数据无论如何指定知识点2 22的难度知识点1 11的难度会产生矛盾。数据规模与约定对于所有测试数据1 ≤ T ≤ 10 5 1 \le T \le 10^51≤T≤1052 ≤ n ≤ 10 5 2 \le n \le 10^52≤n≤105− 1 ≤ a i ≤ 10 9 -1 \le a_i \le 10^9−1≤ai​≤1091 ≤ u , v ≤ n 1 \le u,v \le n1≤u,v≤n。保证单个测试点中所有测试数据的n nn的和不超过2 × 10 5 2 \times 10^52×105每组测试数据输入的所有边构成一棵以1 11为根的外向树。后记大纲发表了。若干天后小 I 给 ION 比赛投题却发现有人偷偷改了一笔难度表导致他的题目超纲。于是小 I 只能把题投给 CPUHT。题目来源来自 2023 清华大学学生程序设计竞赛暨高校邀请赛THUPC2023决赛。题解等资源可在 https://github.com/THUSAAC/THUPC2023 查看。C实现#includebits/stdc.hintread(){intx;scanf(%d,x);returnx;}constintDUST327,N114514,M-1;inthead[N],to[N],ne[N],idx10;voidadd(intu,intv){to[idx1]v,ne[idx1]head[u],head[u]idx1;}inta[N];boolub[N];//ub[u] true 代表该点点权未确定即取值范围上不封顶booldfs(intu){intmx-1,cnt0;boolflag0;for(intihead[u];~i;ine[i]){intvto[i];if(dfs(v)0)return0;if(a[v]mx)mxa[v],cnt1;elseif(a[v]mx)cnt;flag|ub[v];}if(cnt0a[u]-1)a[u]0,ub[u]1;//叶子节点else/**/if(cnt){intxmx(cnt1);//minimum possibleif(a[u]!-1){if(a[u]x)return0;/**/if(!flaga[u]!x)return0;return1;}//a[u] -1if(a[u]-1flag)ub[u]1;a[u]x;}return1;}intmain(){intTread();while(T--){intnread();idx10;for(inti1;in;i)head[i]-1,ub[i]0;for(inti1;in;i)a[i]read();for(inti1;in;i){inturead(),vread();add(u,v);}puts(dfs(1)?Reasonable:Unreasonable);}}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容