题目：给定一棵包含 N个顶点的树。顶点编号为 1 至 N，第 i条边 (1≤i≤N−1) 连接顶点 ai与顶点 bi。 对于树中任意两个顶点 u 和 v（满足 u<v），定义距离 d(u,v)为连接 u 和 v的简单路径上的边的数量。 请计算所有满足 u<v的顶点对 (u,v) 的距离 d(u,v) 的总和。 输入格式 第一行 ，一个整数表示n 接下来的n−1行，每行两个整数ai,bi. 输出格式 输出所有满足 u<v的顶点对 (u,v) 的距离 d(u,v)的总和。 输入样例#1 3 1 2 2 3 输出样例#1 3 输入样例#2 5 1 2 1 3 1 4 1 5 输出样例#2 10 说明提示 【 数据范围 】 2≤N≤105 1≤ai,bi≤N 限制 时间限制：1000ms 内存限制：256MiB

题目：公平 题目描述 有多干所精英学院和 N 名天才学员（编号 1 到 N）。每名学员 i拥有能力值 Ai 和初始所属学院 Bi。 联盟定期进行学员调院操作（共 Q 次）：第 j次操作将学员 Cj 调到学院 Dj。 联盟公平指数定义为： 对每所至少有一名学员的学院，取该学院最高能力值；再取这些最高能力值中的最小值。 请计算每次调院操作后的联盟公平指数。 输入格式 · 第一行：N Q · 接下来 N 行：每行 Ai Bi，表示学员 ii 的能力值和初始学院 · 接下来 Q 行：每行 Cj Dj，表示将学员 Cj 调到学院 Dj 输出格式 · Q 行：每行一个整数，表示每次操作后的公平指数 输入样例#1 6 3 8 1 6 2 9 3 1 1 2 2 1 3 4 3 2 1 1 2 输出样例#1 6 2 6 输入样例#2 2 2 4208 1234 3056 5678 1 2020 2 2020 输出样例#2 3056 4208 说明提示 1≤N,Q≤2×105，1≤N,Q≤2×105 1≤Ai≤109，1≤Ai≤109 1≤Cj≤N，1≤Cj≤N 1≤Bi,Dj≤2×105，1≤Bi,Dj≤2×105 输入均为整数 每次转园操作会改变所属学院 限制 时间限制：1000ms 内存限制：256MiB

题目：花车巡游 题目描述 嘉年华的花车巡游正在展示精心编排的队列变换！ 最初，所有 N辆花车排成一行，花车 i 位于第 i 位。变换程序由 K 个位置对 (a1,b1),(a2,b2),…,(aK,bK) 描述。表演过程中： · 第 1 分钟：位置 a1 与 b1 的花车交换位置 · 第 2 分钟：位置 a2 与 b2 的花车交换位置 · …… · 第 K 分钟：位置 aK 与 bK 的花车交换位置 · 第 K+1 分钟：重新从 (a1,b1) 开始交换（即位置 a1 与 b1 交换） · 第 K+2 分钟：位置 a2 与 b2 交换 · 如此无限循环…… 请计算每辆花车在整个表演过程中能到达的不同位置数量。 输入格式 第一行输入 N,K。 接下来 K 行每行包含 ai,bi（1≤ai<bi≤N）。 输出格式 输出 N行，第 i行为花车 i能到达的不同位置数量。 输入样例 5 4 1 3 1 2 2 3 2 4 输出样例 4 4 3 4 1 说明提示 样例解释 · 花车 1 可到达位置 {1,2,3,4} · 花车 2 可到达位置 {1,2,3,4} · 花车 3 可到达位置 {1,2,3} · 花车 4 可到达位置 {1,2,3,4} · 花车 5 始终在位置 5（未移动） 【数据范围】 1≤K≤2×105 2≤N≤105 限制 时间限制：1000ms 内存限制：256MiB

题目：数字之和 题目描述 给定一个数字字符串 n，定义一次操作为：移除字符串中一个非空子串，并将剩余部分拼接形成新数字。 求所有可能操作方案生成的新数字之和，结果对 109+7取模。 输入格式 一行字符串 n 输出格式 一个整数，表示所有方案生成数字之和取模后的结果。 输入样例#1 1003 输出样例#1 339 输入样例#2 123 输出样例#2 52 说明提示 【数据范围】 1≤∣n∣≤105,| n |表示字符串长度。 限制 时间限制：1000ms 内存限制：256MiB

题目：4.# 工作规划## 题目描述n*n* 台机器人正在完成任务。其中，第 i*i* 台机器人需要工作 ti*ti* 分钟才能完成任务。这些机器人之间有一些前后约束，其中约束关系共有m*m*条，每一条约束表示机器人 b*b* 要在机器人 a*a* 完成任务后才能开始工作。请问，所有机器人任务完成最少需要花多少时间。保证所有约束之间均是合理的，所有机器人一定在有限时间内完成工作。## 输入格式第一行：两个整数 n*n* 和 m*m*• 第二行到第 n+1*n*+1 行：每个机器人需要的时间 ti*ti*​• 接下来 m*m* 行：每行有两个整数 a*a* 和 b*b*，表示第 b*b* 台机器人必须要等第 a*a* 台机器人任务完成之后才能开始工作。## 输出格式单个整数，表示所有机器人任务完成最少需要花多少时间。## 输入样例10 932913518228294123 24 81 76 57 108 110 92 45 3## 输出样例161## 说明提示1≤n≤1041≤*n*≤1041≤m≤50,0001≤*m*≤50,0001≤ti≤1051≤*ti*​≤1051≤ai,bi≤n1≤*ai*​,*bi*​≤*n*## 限制时间限制：1000ms内存限制：512MiB

题目：3.# 联盟## 题目描述在国际会议上，共有 n*n* 个国家需要加入三个联盟中的一个。任何两个接壤的国家不能加入相同的联盟。现在给出各国的接壤情况，请计算存在多少种合法的联盟分配方案。## 输入格式· 第一行：单个整数 n*n* 表示国家数量· 第二行到第 n*n* 行：在第 i+1*i*+1 行有 n−i*n*−*i* 个整数 ci,i+1,ci,i+2,…,ci,n*ci*,*i*+1,*ci*,*i*+2,…,*ci*,*n*，其中· ci,j=0*ci*,*j*=0 表示 i*i* 号国家与 j*j* 号国家不接壤· ci,j=1*ci*,*j*=1 表示 i*i* 号国家与 j*j* 号国家接壤## 输出格式单个整数：表示合法的联盟分配方案总数。## 输入样例#131 11## 输出样例#16## 输入样例#241 1 11 11## 输出样例#20## 说明提示数据范围· 对于 50%50% 的数据，1≤n≤121≤*n*≤12· 对于 100%100% 的数据，1≤n≤201≤*n*≤20样例1说明三国两两接壤，形成三角形。三个联盟的排列方案为 3!=63!=6 种。## 限制时间限制：1000ms内存限制：512MiB

题目：2.# 逻辑表达式## 题目描述给定一个逻辑表达式，以运算符做前缀的形式给出。它包含三种运算符：&、|、^：· & 表示逻辑与运算· | 表示逻辑或运算· ^ 表示逻辑异或运算表达式还包含三种基本逻辑值：0、1、?。每个 ? 必须赋值成为 0 或 1 中的一种，请问有多少种不同的赋值方式，可以让整个逻辑表达式的值为 0？由于答案可能很大，请输出方案数模 1,000,000,0071,000,000,007 的余数。前缀表达式的定义如下：· 0、1、? 都是前缀表达式；· 如果 x，y 都是前缀表达式，则 &xy、｜xy、^xy 都是前缀表达式；· 不满足以上两条规则的表达式都不是前缀表达式。## 输入格式单个字符串表示输入的前缀表达式## 输出格式单个整数：表示答案模 1,000,000,0071,000,000,007 的余数。## 输入样例#1&??## 输出样例#13## 输入样例#2||??|||?^?|0|1&???|??## 输出样例#24## 输入样例#3|?^?|0|&??||?^?|1??## 输出样例#364## 说明提示设 ∣s∣∣*s*∣ 表示输入字符串的长度· 50%50%的数据，1≤∣s∣<1,0001≤∣*s*∣<1,000· 100%100%的数据，1≤∣s∣<200,0001≤∣*s*∣<200,000## 限制时间限制：1000ms内存限制：512MiB

题目：1.# 子序列## 题目描述给定两个整数序列，第一个序列长度为 n*n*，第二个序列长度为 m*m*。请问，这两个序列有多少种公共的子序列？输出数量模 998244353998244353 的余数。所谓子序列，是指从原序列中选择部分或全部元素组成新序列，这些元素在原序列中不必连续，但要保持在原序列中的顺序。只要下标不同，哪怕数字相同，也要算成不同的子序列。## 输入格式· 第一行：两个整数表示 n*n* 与 m*m*；· 第二行： n*n* 个数字 a1,a2,⋯ ,an*a*1,*a*2,⋯,*an*；· 第三行：m*m* 个数字 b1,b2,⋯ ,bm*b*1,*b*2,⋯,*bm*；## 输出格式单个整数表示答案。## 输入样例4 33 4 6 23 3 2## 输出样例6## 说明提示· 1≤n,m≤20001≤*n*,*m*≤2000· 1≤ai,bj≤100,0001≤*ai*,*bj*≤100,000## 限制时间限制：1000ms内存限制：512MiB

题目：4.是不是堆二叉堆可以用一棵完全二叉树来实现，但完全二叉树不一定满足堆的性质。本题就请你判断一棵给定的完全二叉树是不是堆。时间限制：1000内存限制：65536输入输入在一行中给出两个正整数：m（≤ 100）是将要测试的完全二叉树的数量；n（1 < n ≤ 1000）是完全二叉树中的结点数。 随后 m 行，每行给出 n 个互不相同的键值（均在整型范围内），为完全二叉树的层序遍历序列。输出对输入的每棵完全二叉树，如果它是最大堆（大顶堆），就在一行中输出 `Max Heap`；如果是最小堆（小顶堆），则输出 `Min Heap`；如果根本不是堆，则输出 `Not Heap`。然后在下一行输出这棵树的后序遍历序列。同行数字间以 1 个空格分隔，行首尾不得有多余空格。样例输入3 898 72 86 60 65 12 23 508 38 25 58 52 82 70 6010 28 15 12 34 9 8 56样例输出Max Heap50 60 65 72 12 23 86 98Min Heap60 58 52 38 82 70 25 8Not Heap56 12 34 28 9 8 15 10

题目：3.树的偏斜度对于一棵二叉树，令 nL 表示仅有左孩子的结点的个数，令 nR 表示仅有右孩子的结点的个数。这棵树的“偏斜度”定义为 Ds = nL - nR。本题就请你计算任一棵给定二叉树的 Ds。时间限制：1000内存限制：65536输入输入在第一行给出正整数 n (≤ 103)，为二叉树中结点个数。随后两行先后给出这棵树的后序遍历和中序遍历序列，键值为 1 到 n 的整数。同行数字间以空格分隔。输出在一行中按以下格式输出树的偏斜度： Ds = nL - nR样例输入71 2 7 5 4 3 61 2 3 4 7 5 6样例输出2 = 3 - 1