万卷网

NOIP提高组

万卷网> 考级竞赛> 信息学奥赛> NOIP提高组

NOIP提高组

更新时间： 2023-09-02 20:23:05 试题数量： 316

我的练习

顺序练习

随机练习

章节练习

错题练习

题库预览

简答题树的重心小简单正在学习离散数学，今天的内容是图论基础，在课上他做了如下两条笔记：1.一个大小为n的树由n个结点与n-1条无向边构成，且满足任意两个结点间有且仅有一条简单路径。在树中删去一个结点及与它关联的边，树将分裂为若干个子树；而在树中删去一条边（保留关联结点，下同），树将分裂为恰好两个子树。2.对于一个大小为n的树与任意一个树中结点c,称c是该树的重心当且仅当在树中删去c及与它关联的边后，分裂出的所有子树的大小均不超过（其中Lx」是下取整函数）。对于包含至少一个结点的树.它的重心只可能有1或2个。课后老师给出了一个大小为n的树S,树中结点从1~n编号。小简单的课后作业是求出S单独删去每条边后，分裂出的两个子树的重心编号和之和。即：上式中，E表示树S的边集，（u，n）表示一条连接u号点和V号点的边。S'u与S'v 分别表示树S删去边（u，v）后，u号点与V号点所在的被分裂出的子树。小简单觉得作业并不简单，只好向你求助，请你教教他。【输入格式】从文件centroid.in中读入数据。本题输入包含多组测试数据。第一行一个整数T表示数据组数。接下来依次给岀每组输入数据，对于每组数据：第一行一个整数n表示树S的大小。接下来n -1行，每行两个以空格分隔的整数 ui，vi，表示树中的一条边（ui，vi）。【输出格式】输出到文件centroid.out中。共T行，每行一个整数.第i行的整数表示：第i组数据给岀的树单独删去每条边后，分裂出的两个子树的重心编号和之和。【样例1输入】251223243571 21 31 43 53 66 7【样例1输出】3256【样例1解释】对于第一组数据:删去边（1,2）, 1号点所在子树重心编号为｛1｝, 2号点所在子树重心编号为｛2,3｝。删去边（2,3）, 2号点所在子树重心编号为⑵，3号点所在子树重心编号为｛3,5｝。删去边（2,4）, 2号点所在子树重心编号为｛2,3｝, 4号点所在子树重心编号为｛4｝。删去边（3,5）, 3号点所在子树重心编号为｛2｝, 5号点所在子树重心编号为｛5｝。因此答案为 1 + 2 + 3 + 2 + 3 + 5 + 2 + 3 + 4 + 2 + 5 = 32。【数据范围】表中特殊性质一栏，两个变量的含义为存在一个1~n的排列使得: A：树的形态是一条链。即存在一条边(pi,pi+1)。B：树的形态是一个完美二叉树。即存在两条边(Pi，P2i)与(Pi，P2i+1)。对于所有测试点：保证给岀的图是一个树。

简答题 Emiya家今天的饭【题目描述】Emiya 是个擅长做菜的高中生，他共掌握 n 种烹饪方法，且会使用 m 种主要食材做菜。为了方便叙述，我们对烹饪方法从 1~n 编号，对主要食材从 1 ~m 编号。Emiya 做的每道菜都将使用恰好一种烹饪方法与恰好一种主要食材。更具体地，Emiya 会做 ai,j 道不同的使用烹饪方法 i 和主要食材 j 的菜（1 ≤i≤n,1≤j≤m），这也意味着 Emiya 总共会做道不同的菜。Emiya 今天要准备一桌饭招待 Yazid 和 Rin 这对好朋友，然而三个人对菜的搭配有不同的要求，更具体地，对于一种包含 k 道菜的搭配方案而言：（1）Emiya 不会让大家饿肚子，所以将做至少一道菜，即 k≥1（2）Rin 希望品尝不同烹饪方法做出的菜，因此她要求每道菜的烹饪方法互不相同（3）Yazid 不希望品尝太多同一食材做出的菜，因此他要求每种主要食材至多在一半的菜（即道菜）中被使用这里的⌊x⌋ 为下取整函数，表示不超过 x 的最大整数。这些要求难不倒 Emiya，但他想知道共有多少种不同的符合要求的搭配方案。两种方案不同，当且仅当存在至少一道菜在一种方案中出现，而不在另一种方案中出现。Emiya 找到了你，请你帮他计算，你只需要告诉他符合所有要求的搭配方案数对质数998,244,353 取模的结果。【输入格式】从文件meal.in中读入数据。第 1 行两个用单个空格隔开的整数 n,m。第 2 行至第 n+1 行，每行 m 个用单个空格隔开的整数，其中第 i + 1行的 m 个数依次为 ai,1,ai,2,⋯,ai,m。【输出格式】输出到文件meal.out中。仅一行一个整数，表示所求方案数对 998,244,353 取模的结果。【样例 1 输入】2 3 1 0 10 1 1【样例 1 输出】3【样例1解释】由于在这个样例中，对于每组i，j，Emiya都最多只会做一道菜，因此我们直接通过给出烹饪方法、主要食材的编号来描述一道菜。符合要求的方案包括：•做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材2的菜•做一道用烹饪方法1、主要食材1的菜和一道用烹饪方法2、主要食材3的菜•做一道用烹饪方法1、主要食材3的菜和一道用烹饪方法2、主要食材2的菜因此输出结果为3 mod 998,244,353 = 3。需要注意的是，所有只包含一道菜的方案都是不符合要求的，因为唯一的主要食材在超过一半的菜中出现，这不满足Yazid的要求。【样例2输入】3 31 2 34 5 06 0 0【样例2输出】190【样例2解释】Emiya必须至少做2道菜。做2道菜的符合要求的方案数为100。做3道菜的符合要求的方案数为90。因此符合要求的方案数为100 + 90 = 190。【样例3输入】5 51 0 0 1 10 1 0 1 01 1 1 1 01 0 1 0 10 1 1 0 1【样例3输出】742【数据范围】对于所有测试点，保证 1 ≤n≤ 100, 1 ≤ m ≤ 2000, 0≤ai，j< 998,244,353。

简答题括号树【题目背景】本题中合法括号串的定义如下：1.0是合法括号串。2.如果A是合法括号串，则(A)是合法括号串。3.如果A, B是合法括号串，则AB是合法括号串。本题中子串与不同的子串的定义如下：1.字符串S的子串是S中连续的任意个字符组成的字符串。S的子串可用起始位置l与终止位置r来表示，记为S(l,r)(1≤l≤r≤|S|,|S|表示S的长度)。2.S的两个子串视作不同当且仅当它们在S中的位置不同，即l不同或r不同。【题目描述】一个大小为n的树包含n个结点和n-1条边，每条边连接两个结点，且任意两个结点间有且仅有一条简单路径互相可达。小Q是一个充满好奇心的小朋友，有一天他在上学的路上碰见了一个大小为n的树，树上结点从1~n编号，1号结点为树的根。除1号结点外，每个结点有一个父亲结点，u (2≤ u≤n)号结点的父亲为fu (1 ≤ fu < u)号结点。小Q发现这个树的每个结点上恰有一个括号，可能是'('或')'。小Q定义si为：将根结点到i号结点的简单路径上的括号，按结点经过顺序依次排列组成的字符串。显然si是个括号串，但不一定是合法括号串，因此现在小Q想对所有的i(1≤i≤n) 求岀，si中有多少个互不相同的子串是合法括号串。这个问题难倒了小Q,他只好向你求助。设si共有ki个不同子串是合法括号串, 你只需要告诉小Q所有ixki的异或和，即：(1 x k1) xor (2 x k2) xor (3 x k3)xor .…xor (n x kn)其中xor是位异或运算。【输入格式】从文件brackets.in中读入数据。第一行一个整数n，表示树的大小。第二行一个长为n的由'('与')'组成的括号串，第i个括号表示i号结点上的括号。第三行包含n-1个整数，第i(1≤i<n)个整数表示i+1号结点的父亲编号fi+1。【输出格式】输出到文件brackets.out中。仅一行一个整数表示答案。【样例1输入】5（（）（）1 1 2 2【样例1输出】6【样例1解释】树的形态如下图:将根到1号结点的简单路径上的括号，按经过顺序排列所组成的字符串为（，子串是合法括号串的个数为0。将根到2号结点的简单路径上的括号，按经过顺序排列所组成的字符串为（（，子串是合法括号串的个数为0。将根到3号结点的简单路径上的括号，按经过顺序排列所组成的字符串为（），子串是合法括号串的个数为1。将根到4号结点的简单路径上的括号，按经过顺序排列所组成的字符串为（（（，子串是合法括号串的个数为0。将根到5号结点的简单路径上的括号，按经过顺序排列所组成的字符串为（（），子串是合法括号串的个数为1。【数据范围】

简答题划分【题目描述】2048年，第三十届CSP认证的考场上，作为选手的小明打开了第一题。这个题的样例有n组数据，数据从1~n编号，i号数据的规模为ai。小明对该题设计出了一个暴力程序，对于一组规模为u的数据，该程序的运行时间为u^2。然而这个程序运行完一组规模为u的数据之后，它将在任何一组规模小于u 的数据上运行错误。样例中的ai,不一定递增，但小明又想在不修改程序的情况下正确运行样例，于是小明决定使用一种非常原始的解决方案：将所有数据划分成若干个数据段，段内数据编号连续，接着将同一段内的数据合并成新数据，其规模等于段内原数据的规模之和.小明将让新数据的规模能够递增。也就是说，小明需要找到一些分界点使得注意P可以为0且此时k0 = 0,也就是小明可以将所有数据合并在一起运行。小明希望他的程序在正确运行样例情况下，运行时间也能尽量小，也就是最小化小明觉得这个问题非常有趣，并向你请教：给定n和ai,请你求出最优划分方案下，小明的程序的最小运行时间。【输入格式】从文件partition.in中读入数据。由于本题的数据范围较大，部分测试点的ai将在程序内生成。第一行两个整数n.type. n的意义见题目描述，type表示输入方式。1.若type = 0.则该测试点的ai直接给出。输入文件接下来：第二行n个以空格分隔的整数ai，表示每组数据的规模。2.若type = 1则该测试点的ai将特殊生成，生成方式见后文。输入文件接下来: 第二行六个以空格分隔的整数x,y,z,b1,b2,m。接下来m行中，第i行包含三个以空格分隔的正整数pi,li,ri。对于type = 1的23 ~ 25号测试点，ai的生成方式如下：给定整数x,y,z,b1，b2，m,以及m个三元组（pi，li，ri）。保证 n2。若 n > 2,则保证对于所有则有ai=（bi mod（rj-lj+1））+lj上述数据生成方式仅是为了减少输入量大小，标准算法不依赖于该生成方式。【输出格式】输出到文件partition.out中。输出一行一个整数，表示答案。【样例1输入】5 05 17 9 9【样例1输出】247【样例1解释】最优的划分方案为{5,1},{7},{9},{9}。由5 + 1<=7<=9<=9知该方案合法。答案为(5 + 1)^2 + 7^2 + 9^2 + 9^2 = 247。虽然划分方案{5}，{1},{7},{9},{9}对应的运行时间比247小，但它不是一组合法方案，因为5>1。虽然划分方案{5},{1,7},{9},{9}合法，但该方案对应的运行时间为251,比247大。【样例2输入】10 05677462 13 19 9【样例2输出】1256【样例2解释】最优的划分方案为{5},{6}，{7}，{7},{4,6，2},{13},{19,9}。【数据范围】所有测试点满足：type € {0,1} , 2 < =n <= 4 x 10^7 , 1 < =ai,<= 10^9 , 1 <=m < =10^5 , 1 < =li <= ri <= 10^9 , 0 < x,y,z,b1,b2 < 2^30。

简答题格雷码【题目描述】通常，人们习惯将所有n位二进制串按照字典序排列，例如所有2位二进制串按字典序从小到大排列为：00, 01, 10, 11格雷码（Gray Code）是一种特殊的n位二进制串排列法，它要求相邻的两个二进制串间恰好有一位不同.特别地，第一个串与最后一个串也算作相邻。所有2位二进制串按格雷码排列的一个例子为：00, 01, 11, 10。n位格雷码不止一种，下面给出其中一种格雷码的生成算法：1.1位格雷码由两个1位二进制串组成，顺序为：0, 1。2.n + 1位格雷码的前2^n个二进制串，可以由依此算法生成的n位格雷码（总共 2^n个n位二进制串）按顺序排列，再在每个串前加一个前缀0构成。3.n + 1位格雷码的后2^n个二进制串，可以由依此算法生成的n位格雷码（总共 2^n个n位二进制串）按逆序排列，再在每个串前加一个前缀1构成。综上，n + 1位格雷码，由n位格雷码的2^n个二进制串按顺序排列再加前缀0,和按逆序排列再加前缀1构成，共2^n+1个二进制串。另外，对于n位格雷码中的2^n个二进制串，我们按上述算法得到的排列顺序将它们从0~2^n - 1编号。按该算法，2位格雷码可以这样推出：1.己知1位格雷码为0, 12.前两个格雷码为00, 01.后两个格雷码为11, 10。合并得到00, 01, 11, 10, 编号依次为0〜3。同理，3位格雷码可以这样推出：1.己知2位格雷码为：00, 01, 11 10。2.前四个格雷码为：000, 001, 011.010。后四个格雷码为：110, 111, 101, 100。合并得到：000, 001. 011, 010, 110, 111. 101, 100,编号依次为 0 ~7。现在给出n，k请你求出按上述算法生成的n位格雷码中的k号二进制串。【输入格式】从文件code.in中读入数据。仅一行两个整数n，k意义见题目描述。【输出格式】输出到文件code.out中。仅一行一个n位二进制串表示答案。【样例1输入】23【样例1输出】10【样例1解释】2位格雷码为：00, 01, 11. 10,编号从0〜3,因此3号串是10。【样例2输入】35【样例2输出】111【样例2解释】3 位格雷码为：000, 001. 011, 010, 110, 111. 101, 100,编号从 0 〜7,因此 5 号串是111。【数据范围】对于50%的数据：n≤ 10对于80%的数据：k≤5x10^6对于95%的数据：k≤ 2^63 - 1对于 100% 的数据：1 ≤ n ≤ 64,0 ≤ k≤2^n

简答题树上的数【题目描述】给定一个大小为n的树，它共有n个结点与n-1条边，结点从1~n编号。初始时每个结点上都有一个1~n的数字，且每个1~n的数字都只在恰好一个结点上出现。接下来你需要进行恰好n-1次删边操作，每次操作你需要选一条未被删去的边, 此时这条边所连接的两个结点上的数字将会交换.然后这条边将被删去。n-1次操作过后，所有的边都将被删去。此时，按数字从小到大的顺序，将数字 1~n所在的结点编号依次排列，就得到一个结点编号的排列Pi。现在请你求出，在最优操作方案下能得到的字典序最小的Pi。如上图，蓝圈中的数字1〜5 一开始分别在结点②、①、③、⑤、④。按照⑴⑷(3)⑵ 的顺序删去所有边，树变为下图。按数字顺序得到的结点编号排列为 ①③④②⑤，该排列是所有可能的结果中字典序最小的。【输入格式】从文件tree.in中读入数据。本题输入包含多组测试数据。第一行一个正整数T,表示数据组数。对于每组测试数据：第一行一个整数n，表示树的大小。第二行n个整数，第i (1≤i≤ n)个整数表示数字i初始时所在的结点编号。接下来n-1行每行两个整数x,y,表示一条连接x号结点与y号结点的边。【输出格式】输出到文件tree.out中。对于每组测试数据，输出一行共n个用空格隔开的整数，表示最优操作方案下所能得到的字典序最小的Pi。【样例1输入】4 52 1 3 5 41 31 42 44 553 4 2 1 51 22 33 44 551 2 5 3 41 21 31 41 5101 2 3 4 5 7 8 9 10 61 21 31 41 55 66 77 88 99 10【样例1输出】1 3 4 2 51 3 5 2 42 3 1 4 5 2 3 4 5 6 1 7 8 9 10【数据范围】对于所有测试点：1 ≤ T ≤ 10，保证给出的是一个树。

简答题铺设道路【问题描述】春春是一名道路工程师，负责铺设一条长度为 n 的道路。铺设道路的主要工作是填平下陷的地表。整段道路可以看作是 n 块首尾相连的区域，一开始，第 i 块区域下陷的深度为 di 。春春每天可以选择一段连续区间 [L, R] ，填充这段区间中的每块区域，让其下陷深度减少 1。在选择区间时，需要保证，区间内的每块区域在填充前下陷深度均不为 0 。春春希望你能帮他设计一种方案，可以在最短的时间内将整段道路的下陷深度都变为 0 。【输入格式】输入文件名为 road.in。输入文件包含两行，第一行包含一个整数 n，表示道路的长度。第二行包含 n 个整数，相邻两数间用一个空格隔开，第 i 个整数为 di 。【输出格式】输出文件名为 road.out。输出文件仅包含一个整数，即最少需要多少天才能完成任务。【输入输出样例 1】【样例解释】一种可行的最佳方案是，依次选择：[1,6]、[1,6]、[1,2]、[1,1]、[4,6]、[4,4]、[4,4]、[6,6]、[6,6]。【数据规模与约定】对于 30% 的数据，1 ≤ n ≤ 10 ；对于 70% 的数据，1 ≤ n ≤ 1000 ；对于 100% 的数据，1 ≤ n ≤ 100000 ，0 ≤ di ≤ 10000 。

单选题下列四个不同进制的数中，与其它三项数值上不相等的是（）。

单选题下列属于解释执行的程序设计语言是（）。

简答题赛道修建【问题描述】C 城将要举办一系列的赛车比赛。在比赛前，需要在城内修建m 条赛道。C 城一共有 n 个路口，这些路口编号为 1,2, … , n，有 n − 1 条适合于修建赛道的双向通行的道路，每条道路连接着两个路口。其中，第 i 条道路连接的两个路口编号为 ai和 bi，该道路的长度为 li。借助这 n − 1 条道路，从任何一个路口出发都能到达其他所有的路口。一条赛道是一组互不相同的道路 e1, e2, … , ek，满足可以从某个路口出发，依次经过道路 e1, e2, … , ek（每条道路经过一次，不允许调头）到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全，要求每条道路至多被一条赛道经过。目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案，使得修建的m条赛道中长度最小的赛道长度最大（即m条赛道中最短赛道的长度尽可能大）。【输入格式】输入文件名为 track.in。输入文件第一行包含两个由空格分隔的正整数 n, m，分别表示路口数及需要修建的赛道数。接下来 n − 1 行，第 i 行包含三个正整数 ai, bi, li，表示第 i 条适合于修建赛道的道路连接的两个路口编号及道路长度。保证任意两个路口均可通过这 n − 1 条道路相互到达。每行中相邻两数之间均由一个空格分隔。【输出格式】输出文件名为 track.out。输出共一行，包含一个整数，表示长度最小的赛道长度的最大值。【输入输出样例 1】【输入输出样例 1 说明】所有路口及适合于修建赛道的道路如下图所示：道路旁括号内的数字表示道路的编号，非括号内的数字表示道路长度。需要修建 1 条赛道。可以修建经过第 3,1,2,6 条道路的赛道（从路口 4 到路口 7），则该赛道的长度为 9 + 10 + 5 + 7 = 31，为所有方案中的最大值。【输入输出样例 2】【输入输出样例 2 说明】所有路口及适合于修建赛道的道路如下图所示：需要修建 3 条赛道。可以修建如下 3 条赛道：1. 经过第 1,6 条道路的赛道（从路口 1 到路口 7），长度为 6 + 9 = 15；2. 经过第 5,2,3,8 条道路的赛道（从路口 6 到路口 9），长度为 4 + 3 + 5 + 4 = 16；3. 经过第 7,4 条道路的赛道（从路口 8 到路口 5），长度为 7 + 10 = 17。长度最小的赛道长度为 15，为所有方案中的最大值。【数据规模与约定】所有测试数据的范围和特点如下表所示其中，“分支不超过 3”的含义为：每个路口至多有 3 条道路与其相连。对于所有的数据，2 ≤ n≤ 50,000，1 ≤ m ≤ n − 1，1 ≤ ai, bi ≤ n，1 ≤ li ≤ 10,000。

单选题中国计算机学会于（）年创办全国青少年计算机程序设计竞赛

简答题货币系统【问题描述】在网友的国度中共有 n 种不同面额的货币，第 i 种货币的面额为 a[i]，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为 n、面额数组为 a[1..n]的货币系统记作 (n,a)。在一个完善的货币系统中，每一个非负整数的金额 x 都应该可以被表示出，即对每一个非负整数 x，都存在 n 个非负整数 t[i] 满足 a[i]× t[i] 的和为 x。然而，在网友的国度中，货币系统可能是不完善的，即可能存在金额 x 不能被该货币系统表示出。例如在货币系统 n=3, a=[2,5,9] 中，金额 1,3 就无法被表示出来。两个货币系统 (n,a) 和 (m,b) 是等价的，当且仅当对于任意非负整数 x，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。现在网友们打算简化一下货币系统。他们希望找到一个货币系统 (m,b)，满足(m,b) 与原来的货币系统 (n,a) 等价，且 m 尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的 m。【输入格式】输入文件名为 money.in。输入文件的第一行包含一个整数 T，表示数据的组数。接下来按照如下格式分别给出 T 组数据。每组数据的第一行包含一个正整数 n。接下来一行包含 n 个由空格隔开的正整数a[i]。【输出格式】输出文件名为 money.out。输出文件共有 T 行，对于每组数据，输出一行一个正整数，表示所有与 (n,a) 等价的货币系统 (m,b) 中，最小的 m。【输入输出样例 1】【输入输出样例 1 说明】在第一组数据中，货币系统 (2, [3,10]) 和给出的货币系统 (n, a) 等价，并可以验证不存在 m < 2 的等价的货币系统，因此答案为 2。在第二组数据中，可以验证不存在 m < n 的等价的货币系统，因此答案为 5。【数据规模与约定】对于 100% 的数据，满足 1 ≤ T ≤ 20, n,a[i] ≥ 1。

简答题保卫王国【问题描述】Z 国有n座城市，n − 1条双向道路，每条双向道路连接两座城市，且任意两座城市都能通过若干条道路相互到达。Z 国的国防部长小 Z 要在城市中驻扎军队。驻扎军队需要满足如下几个条件：一座城市可以驻扎一支军队，也可以不驻扎军队。由道路直接连接的两座城市中至少要有一座城市驻扎军队。在城市里驻扎军队会产生花费，在编号为i的城市中驻扎军队的花费是pi。小 Z 很快就规划出了一种驻扎军队的方案，使总花费最小。但是国王又给小 Z 提出了m个要求，每个要求规定了其中两座城市是否驻扎军队。小 Z 需要针对每个要求逐一给出回答。具体而言，如果国王提出的第j个要求能够满足上述驻扎条件（不需要考虑第 j 个要求之外的其它要求），则需要给出在此要求前提下驻扎军队的最小开销。如果国王提出的第j个要求无法满足，则需要输出-1 (1 ≤ j ≤ m)。现在请你来帮助小 Z。【输入格式】输入文件名为 defense.in。第 1 行包含两个正整数n, m和一个字符串type，分别表示城市数、要求数和数据类型。type是一个由大写字母 A，B 或 C 和一个数字 1，2，3 组成的字符串。它可以帮助你获得部分分。你可能不需要用到这个参数。这个参数的含义在【数据规模与约定】中有具体的描述。第2行n个整数pi，表示编号i的城市中驻扎军队的花费。接下来n − 1行，每行两个正整数u, v，表示有一条u到v的双向道路。接下来m行，第j行四个整数a, x, b, y(a ≠ b)，表示第j个要求是在城市a驻扎x支军队，在城市b驻扎y支军队。其中，x 、 y 的取值只有 0 或 1：若 x 为 0，表示城市 a 不得驻扎军队，若 x 为 1，表示城市 a 必须驻扎军队；若 y 为 0，表示城市 b 不得驻扎军队，若 y 为 1，表示城市 b 必须驻扎军队。输入文件中每一行相邻的两个数据之间均用一个空格分隔。【输出格式】输出文件名为 defense.out。输出共m行，每行包含 1 个整数，第j行表示在满足国王第j个要求时的最小开销，如果无法满足国王的第j个要求，则该行输出-1。【输入输出样例 1】【样例解释】对于第一个要求，在 4 号和 5 号城市驻扎军队时开销最小。对于第二个要求，在 1 号、2 号、3 号城市驻扎军队时开销最小。第三个要求是无法满足的，因为在 1 号、5 号城市都不驻扎军队就意味着由道路直接连接的两座城市中都没有驻扎军队。【数据规模与约定】对于 100%的数据，n, m ≤ 300000,1 ≤ pi ≤ 100000。数据类型的含义：A：城市i与城市i + 1直接相连。B：任意城市与城市 1 的距离不超过 100（距离定义为最短路径上边的数量），即如果这棵树以 1 号城市为根，深度不超过 100。C：在树的形态上无特殊约束。1：询问时保证a = 1, x = 1，即要求在城市 1 驻军。对b, y没有限制。2：询问时保证a, b是相邻的（由一条道路直接连通）3：在询问上无特殊约束。

简答题填数游戏【问题描述】小 D 特别喜欢玩游戏。这一天，他在玩一款填数游戏。这个填数游戏的棋盘是一个n × m的矩形表格。玩家需要在表格的每个格子中填入一个数字（数字 0 或者数字 1），填数时需要满足一些限制。下面我们来具体描述这些限制。为了方便描述，我们先给出一些定义：• 我们用每个格子的行列坐标来表示一个格子，即（行坐标，列坐标）。（注意：行列坐标均从 0 开始编号）• 合法路径 P：一条路径是合法的当且仅当：1. 这条路径从矩形表格的左上角的格子(0,0)出发，到矩形的右下角格子(n − 1, m − 1)结束；2. 在这条路径中，每次只能从当前的格子移动到右边与它相邻的格子，或者从当前格子移动到下面与它相邻的格子。例如：在下面这个矩形中，只有两条路径是合法的，它们分别是p1：(0,0) → (0,1) →(1,1)和p2：(0,0) → (1,0) → (1,1)。对于一条合法的路径 P，我们可以用一个字符串w(P)来表示，该字符串的长度为n +m − 2，其中只包含字符“R”或者字符“D”，第 i 个字符记录了路径 P 中第 i 步的移动方法，“R”表示移动到当前格子右边与它相邻的格子，“D”表示移动到当前格子下面与它相邻的格子。例如，上图中对于路径p1，有w(P1) = "RD"；而对于另一条路径p2，有w(P2) = "DR"。同时，将每条合法路径 P 经过的每个格子上填入的数字依次连接后，会得到一个长度为n + m − 1的 01 字符串，记为 s(P)。例如，如果我们在格子(0,0)和(1,0)上填入数字0，在格子(0,1)和(1,1)上填入数字 1（见上图红色数字）。那么对于路径p1，我们可以得到s(P1) = "011",对于路径p2，有s(P2) = "001"。游戏要求小 D 找到一种填数字 0、1 的方法，使得对于两条路径p1，P2，如果w(P1) >w(P2)，那么必须s(P1) ≤ s(P2)。我们说字符串 a 比字符串 b 小，当且仅当字符串 a 的字典序小于字符串 b 的字典序，字典序的定义详见第一题。但是仅仅是找一种方法无法满足小 D 的好奇心，小 D 更想知道这个游戏有多少种玩法，也就是说，有多少种填数字的方法满足游戏的要求？小 D 能力有限，希望你帮助他解决这个问题，即有多少种填 0、1 的方法能满足题目要求。由于答案可能很大，你需要输出答案对109 + 7取模的结果。【输入格式】输入文件名为 game.in。输入文件共一行，包含两个正整数 n、m，由一个空格分隔，表示矩形的大小。其中 n 表示矩形表格的行数，m 表示矩形表格的列数。【输出格式】输出文件名为 game.out。输出共一行，包含一个正整数，表示有多少种填 0、1 的方法能满足游戏的要求。注意：输出答案对 10^9+7 取模的结果。【输入输出样例 1】【样例解释】对于2 × 2棋盘，有上图所示的 12 种填数方法满足要求。【输入输出样例 2】【输入输出样例 3】【数据规模与约定】

简答题旅行【问题描述】小 Y 是一个爱好旅行的 OIer。她来到 X 国，打算将各个城市都玩一遍。小 Y 了解到，X 国的n 个城市之间有 m 条双向道路。每条双向道路连接两个城市。不存在两条连接同一对城市的道路，也不存在一条连接一个城市和它本身的道路。并且，从任意一个城市出发，通过这些道路都可以到达任意一个其他城市。小 Y 只能通过这些道路从一个城市前往另一个城市。小 Y 的旅行方案是这样的：任意选定一个城市作为起点，然后从起点开始，每次可以选择一条与当前城市相连的道路，走向一个没有去过的城市，或者沿着第一次访问该城市时经过的道路后退到上一个城市。当小 Y 回到起点时，她可以选择结束这次旅行或继续旅行。需要注意的是，小 Y 要求在旅行方案中，每个城市都被访问到。为了让自己的旅行更有意义，小 Y 决定在每到达一个新的城市（包括起点）时，将它的编号记录下来。她知道这样会形成一个长度为n 的序列。她希望这个序列的字典序最小，你能帮帮她吗？对于两个长度均为 n 的序列 A 和 B，当且仅当存在一个正整数 x，满足以下条件时，我们说序列 A 的字典序小于 B。⚫ 对于任意正整数 1 ≤ i < x，序列 A 的第 i 个元素 Ai 和序列 B 的第 i 个元素Bi 相同。⚫ 序列 A 的第 x 个元素的值小于序列 B 的第 x 个元素的值。【输入格式】输入文件名为 travel.in。输入文件共 m + 1 行。第一行包含两个整数 n, m(m ≤ n) ，中间用一个空格分隔。接下来 m 行，每行包含两个整数 u, v (1 ≤ u, v ≤ n) ，表示编号为 u 和 v 的城市之间有一条道路，两个整数之间用一个空格分隔。【输出格式】输出文件名为 travel.out。输出文件包含一行，n 个整数，表示字典序最小的序列。相邻两个整数之间用一个空格分隔。【输入输出样例 1】【输入输出样例 2】【数据规模与约定】对于 100% 的数据和所有样例，1 ≤ n ≤ 5000 且 m = n − 1 或 m = n 。对于不同的测试点，我们约定数据的规模如下：