浅谈数据的合理组织

1、浅谈数据的合理组织【摘要】信息学是一门高深的学科，它正在高速的发展。随着信息学的发展，其题目中的关系也变得越来越错宗复杂，给我们解题带来困难。对数据进行合理地组织，正是我们面对上述题目时的一种有效手段。本文用几几个经典典例题从从数据的的结构和和顺序两两个方面面进行合合理组织织，达到到优化模模型或是是提升算算法效率率的目的的。介绍绍了“合合理组织织数据”在信息息学中建建立模型型和优化化算法方面面的一些应用用，例题题包含了了动态规规划、数数据结构构、图论论类型的的题目。目的在在于引起起读者对于于数据的的合理组组织的关关注，并并在今后后的解题题中能积极并灵灵活地运运用这一一手段。【关键字字】组织数据

2、据数据据结构动态规规划图图树序列【正文】【引言】一个简单单的例子：给出N个个数字(数字会会比较大大)，然后给给出一些些询问，询问一一个数字字有没有有在给出出的N个数字字当中。当然我们们有很多多已知的的办法：HASHH表、TRRIE、预排序序+二分查查找这些算法法都是通通过对数数据进行行合理的的组织而而起到了了减少工工作量的的作用。不同的是是HASSH表和和TRIIE是利利用数据据形式的的重新组组织，而而预排序序二分分查找是是通过对对数据顺顺序的重重新组织织来达到到优化算算法的目目的的。我们组组织数据据，主要要就是通通过从“形式”和“顺顺序”这这两个角角度来考考虑。事事实上，这两个个方面在在实际

3、运运用中往往往不是是独立的的，通常常需要联联合运用用。我们已经经学习了了很多经经典的数数据结构构，它们们都是合合理组织织数据的的表现。在优化化算法中中有很好好表现。对数据据组织的的合理化化，不仅仅在我们们设计算算法时能能起到优优化程序序效率的的作用，有时，我们在在建立解解题模型型时，合合理地组组织数据据可能给给我们提提供新的的思考角角度，从从而优化化解题模模型，例例一就是是这样的的一个例子子。例一金明的的预算方方案及其其加强版版金明的预预算方案案【题意描描述】给出N个个物品，每个物物品都有有一个权权值(500000)和一个个价格(1000000)。我我们称可可以直接接被购买买的物品品为主件件，

4、称不不能被直直接购买买的物品品为附件件，附件件只有当当其主件件被购买买了才能能被购买买，一个个主件最最多有两两个附件件，附件件没有下下一级附附件。任务购买买一些物物品，总总价格不不超过MM，使得得被购买买的物品品的权值值之和最最大。N32200 M660【简要分分析】我们很容容易联想想到经典典的动态态规划之之0-1背包问问题。但是题目目与背包包却有一一些差别别：附件件不能被被直接购购买。【对数据据的初步步组织】主件与附附件之间间是树形形的关系系。组织织一下数数据，如如下图：（图1）如图所示示：主件1没没有附件件，主件件2有两个个附件，主件33只有一一个附件件。【数据组组织方案案一】假设我们们忽

5、略数数据的特特殊性，单从树树结构考考虑，我我们容易易想到的的一个算算法是：给所有主主件加上上一个“级超主主件”，把原来来的所有有主件都都变成“超级主主件”的的附件，如下图图： (图22)【算法一一】这样，在在这棵树树上，我我们可以以设计一一个动态态规划算算法：定义：costta表示a节点所所代表的的物品的的价格scorreaa表示示a节点所所代表的的物品的的得分状态fab表表示以节节点a为根的的子树，总共花花费不超超过b元的最最多得分分。状态转移移方程：fab=Maaxffc11bb1+fcc2b2+fc3b33.fckbkk+scoorea;其中cii为a的子节节点；bi=b-ccostta

6、;这样枚举举的效率率显然不不高！我们可以以用左儿儿子右兄兄弟表示示法来表表示这一一棵树，将原树树转化成成二叉树树，则我我们在进进行状态态转移的的时候只只用考虑虑给左儿儿子分配配多少钱钱。leftta表示a的左儿儿子righhtaa表示示a的右儿儿子fab=MaaxMMaxfllefttabblefft+frrighhtaab-ccostta-blleftt+scoorea,frrighhtaab这样我们们可以得得到一个个理论 参见算法艺术与信息学竞赛贪食的九头龙中对算法复杂度的分析复复杂度为为O(NNM2)的算法法，但是是对于本本题的数数据范围围来说，这个复复杂度并并不太理理想。【数据组组织方

7、案案二】上面我们们把本题题同0-1背包进进行了类类比。发发现两道道题之间间的差别别：附件件不能被被直接购购买。显显然，如如果题目目中没有有附件，那么本本题即为为标准的的01背包包问题。我们回到到题目并并考虑其其特殊性性：1.附件件没有附附件。2.每个个主件最最多只有有2个附件件。这样，显显然对于于（图一一）中每每一组（主件附件），可以以作为整整体考虑虑。对于每一一组，可可能的购购买方案案最多只只有：1.什么么都不买买2.只购购买主件件3.购买买主件和和附件114.购买买主件和和附件225.购买买主件和和两个附附件这样，我我们可以以借鉴经经典的001背包包动态规规划，把把每一组组看作一一个对象象

8、，取值值和花费费对应最最多五种种。【算法二二】costtik表示分分组后第第i个对象象的第kk种购买买方案的的花费。weigghtik表表示分组组后第ii个对象象的第kk种购买买方案的的总权值值。Fij表示前前i个对象象最多花花费j元，能能得到的的最大权权值。Fij=maax(FFi-1j-ccosttik+wweigghtik);其中1=k=5且且cosstiikk=j状态总数数：O(NM)转移代价价：O(1)这样，我我们得到到了一个个时间复复杂度为为O(NNM)的的优秀算法法。郁闷的金金明【题意描描述】给出N个个物品，可以直直接被购购买的称称为主件件，而不不能直接接被购买买的称为为附件，附

9、件只只有当其其主件被被购买了了才能被被购买，一个主主件可以以有任意意多个附附件，附附件没有有下一级级附件。每个物物品都有有一个权权值(500000)。任务购买买一些物物品，总总价格不不超过MM，使得得被购买买的物品品的权值值之和最最大。N600M=cosstii),Fi+11jj00情况III：第i个物品品是附件件如果k=1 FFijk= MMaxFii+1j-cosstii1+weiightti(j=coosti),Fi+11jj11如果k=0 FFijk= FFi+1j0状态总数数：O(NM)转移代价价：O(1)时间复杂杂度同样样是O(NM)。很郁闷的的金明【题意描描述】给出N个个物品，可

10、以直直接被购购买的称称为主件件，而不不能直接接被购买买的称为为附件，附件只只有当其其主件被被购买了了才能被被购买，一个主主件可以以有任意意多个附附件，附附件可以以有多级级，也就就是说如如果某个个物品是是附件，那么它它还有可可能有附附属于它它的下一一级附件件。每个个物品都都有一个个权值(5000000)。任务购买买一些物物品，总总价格不不超过MM，使得得被购买买的物品品的权值值之和最最大。N600M32200【问题分分析】现在题目目在原题题的基础础上不仅仅放宽了了附件的的个数，还放宽宽了附件件的层数数，如图所所示：从上图中中，我们们可以对对本题有有一个感感性的认认识：关系又又“宽”又“深深”。我

11、们依然然试着从从前面的的题目中中寻找算算法：我们可以以直接套套用算法法1，因为为该算法法正好将将数据作作为树结结构来进进行处理理。而利利用了题题目特殊殊条件的的算法22和算法法3，直接套套用算法法肯定是是行不通通的。但是他们们都很有有启发性性：抛弃弃树形的的结构，重新组组织成线线形。现在的题题目是不不是也可可以类似似解决呢呢？【组织数数据方案案四】算法3相相对来说说比较算算法2更加一一般，所所以现在在我们再再回过头头来研究究一下算算法3，希望望在分析析过程中中找到一一些灵感感。回忆算法法3的思路路：把同在一一个组的的主件放放在附件件的前面面，利用用动态规规划“加加一维”的思想想，顺利利地实现现

12、了将问问题转化化到序列列上来。关键字：主件在在前序序列动动态规划划我们联想想到利用用树的先先根遍历历序，而而且正好好满足上上面的关关系。但是这样样有什么么好处吗吗？还能能进行动动态规划划吗？怎样设设计状态态才能传传递父节点的状状态呢？我们再回回过去看看算法33的状态态转移：假设当前前状态是是Fiijjkk，且且k=00。如果i是是附件，那么实实际上在在到达下下一个主主件以前前，i后面的的附件是是都不会会被购买买的。上图中，对于附附件a，实际际上一个个k=00的状态态传递下下去是没没有意义义的，因因为附件件b和附件件c也必然然不能被被购买。思考并总总结上面面的结论论：对于一个个主件，我们如如果不

13、购购买的话话，那么么其附件件我们都都不用考考虑，而而直接“跳”到到下一个个主件。我们把它它应用到到本题中中来：重要结论论我们考考虑一棵棵子树的的时候，如果我我们不购购买其根根节点，那那么其子子树中所所有节点点我们都都不必讨讨论了。这一结论论似乎很很显然，但是我我们并不不是要在在树结构构中用这这一结论论。正如如上面提提到的，我们要要在树的的先根遍遍序上进进行动态态规划，而这一一结论正正是我们们成功的的关键。【算法44】根据前面面的思考考，我们们先依次次求出每每棵树的的先根遍遍历序，并保存存在同一一个序列列lisst中。为了利用用上面的的结论，我们还还要求出出以节点点i为根的的子树的的节点总总数c

14、oountti。现在我们们来设计计动态规规划算法法：定义：costti表示第第i个物品品的价格格weigghti表表示第ii个物品品的权值值Fij表示从从第i个物品品到第nn个物品品，最多多花费jj元，能能得到的的最大权权值和。状态转移移：对于一个个节点，我们考考虑是否否购买它它：购买：那那么我们们继续考考虑它后后面的节节点不购买：那么我我们跳过过它的子子孙节点点方程如下下：Fij=MaaxFFi+1j-ccosttliisti+weiighttliisti,Fi+ccounntllisttij这个算法法依然是是O(NNM)的的，很完完美地解解决了本本题。并并且，这个算算法模型型对于以以前有很

15、很多类似似的树形形动态规规划题目目都适用用，这是是我们在在分析本本题的过过程中的意外外收获。【小结】这是一道道很有启启发性的的道目。反思这这一题的的几个不不同难度度的版本本，不难难发现我我们最终终都用线线形模型型上的动动态规划划取代了了容易想想到的树树形动态态规划算算法。我我们再次次分析前前面的算算法，试试图发现现其中内内在的一一些东西西。其实我我们这个个题主要要就是对对于树形形结构和和线形结结构的选选择，所所以我们们对比算算法4和算法法1:不难难发现，相比算算法4，算法法1其实多多出的操操作就是是枚举分分配给左左儿子多多少钱。而在线形形的序列列上，没没有用的的钱自然然地被分分配给后后面的元元

16、素。也也就是说说：树的的形态决决定了在在状态转转移的时时候要进进行额外外的枚举举。这正正是树形形动态规规划算法法的瓶颈颈所在！而我们们利用树树的先根根遍历序序将转树树形转化化为线形形序列，成功地地避免了了树形形形态的限限制，正正是合理理地组织织数据。我们得到到的启示示：凭第一感感觉想出出来的模模型不一一定是最最好的，对于一一个题目目，我们们充分挖挖掘其数数据关系系并加以以利用，合理地地组织数数据并且且尝试用用已有的的知识来来解决，推陈出出新，才才能不断断地进步步。前面我们们在树据据的组织织结构上上进行了了合理地地安排，成功地地对于每每一次加加强的题题目都设设计出了了优秀的的算法，下面，我们来来

17、看一看看“顺序序”的合合理安排排的例子子：例二树的果果实【题意描描述】给出一棵棵有N个节点点的有根根树（根根为1号节点点），每每个节点点有权值值。要求对于于每一个个节点，求：1.其子子树中权权值比该该节点大大的节点点总数2.树上上除其子子孙节点点外比该该节点大大的节点点总数3.从根根节点到到该节点点路径中中比该节节点大的的节点总总数其中(11=NN=1105)【问题分分析】对于要求求的后面面两个值值，我们们很容易易想到OO(Nllog22(N)的算算法：树上除其其子孙节节点外比比该节点点大的节节点总数数：直接排排序，在在待统计计节点前前的与该该节点权权值不同同的个数数再减去去问题11的答案案即

18、为所所求。从根节点点到该节节点路径径中比该该节点大大的节点点总数：以权值值为关键键字构造造线段树树(若权值值大可行行离散化化处理)，深度度优先遍遍历树上上节点，用栈记记录下到到节点的的路径，并把当当前节点点插入线线段树，在线段段树中我我们记录录区间的的元素个个数，当当前节点点权值到到最大权权值这个个区间中中元素个个数即为为所求，我们再再递归处处理子树树，在子子树访问问完毕后后还须把该该节点从从线段树树中删除除。我们最大大的困难难在于求：其子子树中权权值比该该节点大大的节点点总数O(N22)的朴素素统计方方法是很很容易想想到的，但是本本题的数数据规模模达到1105，O(NN2)的复杂杂度显然然太

19、高。我们自自然想到到利用线段段树、树树状数组组这些优优秀的统统计数据据结构来来进行题题目中要要求的统统计任务务。但是这这些数据据结构都都是用于于线型序列列统计的的，并且且似乎没没有改造造版本用用于树形形结构。既然没有有办法改改造数据据结构，那么我我们转换换数据形形态把树转转化为序序列再进进行统计计，先根根遍历序序即是我我们转换换后的理理想形态态。我们给出出一个例例子：同一棵子子树构成成一个连连续的区区间，这这正方便便了我们们的统计计。我们定义义：一个元素素所在子子树在遍遍历序中中构成的的区间叫叫作元素素所在区区间。元素相比比较都指指其权值值大小相相比较。现在问题题已经转转化成为为：给出一个个序

20、列，每个元元素有权权值。对对于每一一个元素素，统计计一个区区间中有有多少元元素比该该元素大大。这正是我我们比较较熟悉的的序列上上的统计计问题。下面我我们研究究转化后后的问题题：【数据组组织方案案一】我们不对对数据进进行更深深入的组织织，直接接利用先先根遍历历序，强强制用数数据结构构来进行行统计。当然我我们可以以构造出一一种比较较有效的的嵌套数数据结构构以有有序表为元元素的线线段树，如图：其中，线线段树的的每一个个节点是是对应区区间的元元素以权权值为关关键字的的有序表表。这样，预预处理可可以用一一个归并并排序，求得树树上所有有区间的的有序表表。时间间复杂度度为O(Nloog2(N)。假设现在在我

21、们要要统计一一个区间间(长度为为L)。那么我们们可以用用logg2(L)的时时间找到到该区间间的所有有分解区区间(不超过过2logg2(L)个)。然后后在对每每个分解解区间进进行处理理：二分分查找在在该区间间中有多多少元素素的权值值比指定定的元素素的权值值大。然后把所所有分解解区间中中比给定定元素大大的元素素个数加加起来，即为所所求。这样每统统计一个个元素的的复杂度度为O(logg22(N)。总时时间复杂杂度为OO(Nllog222(N)，空间间复杂度度为O(Nloog2(N)。【数据组组织方案案二】我们从特特殊情况况考虑：假设我我们在先先根遍历历序中，需要统统计元素素k，并且k所在区区间里的

22、的元素都都比它大大。显然，这这时比k大的元元素个数数就是kk所在区区间中的的元素个个数。统统计区间间元素个个数我们们可以直直接利用用线段树树和树状状数组。那么我们们如何保保证当前前列表中中的元素素权值都都比k的权值值大呢？我们重新新组织数数据：所所有元素素按从大大到小的的顺序排排序。然然后依次次处理每每一个元元素：先先取得所所在区间间的元素素个数，再将该该元素插插入。我们一个个很巧妙妙的方法法：从大大到小地地向线段段树里面面加入元元素，然然后统计计区间个个数。从大到小小保证了了现有的的所有元元素都比比待插入入的元素素大。所所以区间间中的元元素个数数即为比比待插入入元素大大的元素素个数。按照从大

23、大到小的的顺序之之前先对对其区间间进行统统计，利利用线段段树或树树状数组组。这样，我我们得到到了复杂杂度为OO(Nllog22(N)的算算法。WC20005何何林同学学的论文文中介绍绍了此题题的另一一解法，复杂度度也为OO(Nllog22(N)。主主要思想想是也是是利用树树的前根根遍历序序，不同同的是他他的算法法是基于于容斥原原理，需需要正反反两次遍遍历树，而我们们这里介介绍的算算法是利利用了“组织数数据的操操作顺序序”这一一手段来来实现的的。有兴兴趣的同同学可以以参见何何林同学学20005年的的论文。“形态”和“顺顺序”这这两种数数据组织织对象在在上面的的两个例例题中分分别对我我们进行行了表

24、演演。下面面我们再再来分析析一个更更经典的的题目：例三航线规规划【题意描描述】给出一个个有N个点M条边的无无向图，两点之之间可能能有多条条边，然然后给出出Q个命令令，命令令共有如如下两种种：1 A B表示删除除一条AA到B的边2 A B表示询问问AB间共共有多少少条关键键边（即即删除改改边后使使得ABB不连通通)数据保证证任意时时刻图都都是连通通的。1 NN 3 * 11041 MM 10051 QQ 1005【问题分分析】显然，我我们可以以轻松地地设计出出一个朴朴素的算算法：用队列保保存所有有边，当当遇到删删边操作作时加上上删除标标记（利利用HAASH我我们可以以做到OO(1)，遇遇到询问问

25、操作时时则枚举举删边然然后用并并查集判判断ABB是否连连通。这这个算法法处理删删边的复复杂度为为O(11)，处理询问问的复杂度度为O(M2)，空间间复杂度度为O(M+NN)。我们经过过思考后后发现，事实上上所谓的的关键边边都是图图上的桥桥(由题目目中的描描述我们们很容易易想到)。而桥桥的数量量是O(N)级级别的。利用上面面的结论论，我们们显然可可以先用用O(EE)的时时间求出出图中所所有的桥桥，然后后再用OO(N22)的时间间求出AAB间的的关键边边的数量量。然而，我我们所优优化后的的程序依依然有很很高的时时间复杂杂度，根根本不能能胜任此此题。我们继续续思考：树上的任任意两点点间只有有一条路路

26、径。也就是说说树上的的任意一一条边都都是关键键边。这这跟我们们的题目目有什么么关系呢呢？显然然，同一一个重连连通分量量(块)中的任任意两点点之间都都没有关关键边。并且，对对于两个个不同的的重连通通分量MM1,MM2：在在进行删删边操作作以前，询问任任意分属属这两个个分量的的两点AAM11,BMM2，询询问的结结果都是是一样的的，即结结果只跟跟分量间间的边有有关系。也就是是说，一一个重连连通分量量可以当当作整体体来考虑虑。【初步组组织数据据】由前面的的思考，我们把把图中的的重连分分量都“缩”成成一个点点。构成成一个新新图，显显然，新新图是一一棵树。如下：这样，对对于ABB的询问问：若AB属属于同

27、一一个重连连通分量量，则没没有关键键边。若AB属属于不同同的重连连通分量量，则转转化为求求两个树树上节点点的距离离。求树上两两个节点点的距离离我们有有现成的的办法，定义：DeptthAA为节节点A的的深度LCA(A,BB)为节节点A和和节点BB的最近近公共祖祖先。那么ABB间的距距离Diis(AA,B)=DeepthhA+DeepthhB-2*DeppthLCAA(A,B)注意一个个细节，即我们们把一个个重连通通分量“缩”成成一个节节点时，事实上上是把分分量里面面的所有有点的深深度都设设为它们们中最小小的那个个深度，即往上上提升(在同一一个重连连通分量量中以深深度最小小的点作作其它点点的代表表

28、)。如此一来来，对于于一个现现成的图图，我们们可以很很快地求求出两点点间的关关键边数数量了。预处理即即为一个个求重连连通分量量的操作作，时间间复杂度度为O(M)。而对于每每一个询询问我们们都可以以O(11)完成成回答。但事实上上这道题题目中的的图是随随时变化化的(有有删边操操作)，这样我我们就不不太好处处理了。如果每次次都求一一次块的的话，复复杂度会会很高。我们思思考怎么么处理这这个问题题：删边边操作会会导致块块的分裂裂。我们们当然可可以只对对被删边边所在的的块进行行处理，但是最最坏情况况下还是是和每次次求一次次块是一一样的。【进一步步组织数数据】现在的问问题是我我们需要要快速地地将一个个块进

29、行行重新求求块，似似乎是没没有现成成的办法法。但是是如果操操作不是是删边，而是加加边呢？显然，在在一棵树树上加上上一条边边，必然然产生环环，伴随随着的就就是新的的重连通通分量产产生。我们只需需要将几几个有关关的块进进行合并并。换句句话说，就是把把一些点点的位置置抬高，并把它它们合并并成一个个块。如如下图：比如我们们加入一一条边AAB，TT=LCCA(AA,B)，那么么我们的的环上的的节点即即为A到到T的路路径中和和B到TT的路径径中的节节点。我我们需要要把环上上的节点点的深度度都减小小到DeepthhT，并且且，我们们提升一一个节点点，其子子孙节点点也要一一同被提提升相同同的高度度。我们研究究

30、发现，如果操操作是加加边的话话，我们们似乎可可以很高高效地处处理。那么我们们当然可可以把操操作反过过来处理理(先处处理后面面的操作作)，这这样就可可以实现现我们所所要达到到我们所所期望的的结果操作作变为只只有加边边和询问问。现在我们们来考虑虑细节实实现：我们需要要用到LLCA，当然可可以用中中序遍历历+RMMQ实现现。而且且，加边边操作并并不影响响LCAA。然后我们们还有一一个提升升一棵子子树的高高度的操操作。即即把一棵棵子树的的所有节节点的DDetpph都减减去同一一个数。显然，我我们可以以求出树树的先根根遍历序序。这样样，同一一棵子树树构成一一个连续续区间。利用线线段树或或树状数数组我们们

31、就可以以用O(logg2(N)的时时间完成成这项操操作。【小结】这是一道道很经典典的题目目。我们们最初利利用“收收缩”的的思想，把图整整理成为为一棵树树，然后后又巧妙妙地将数数据从后后往前处处理，把把原题中中的“删删边操作作”操作作变成了了“加边边操作”。既有有“形态态”，又又有“顺顺序”上上的考虑虑。在细细节实现现中，我我们又利利用了树树的两大大遍历序序中中序遍历历和前序序遍历，把树上上的求LLCA操操作和提提升子树树的操作作变成了了序列上上的求RRMQ操操作和给给一个区区间所有有元素减减去一个个值的操操作。无无处不体体现出“对数据据的合理理组织”。【总结】“对数据据的合理理组织”无处不不在

32、，它它不仅仅仅是一种种手段，更是竞竞赛的一一种思考考方向。在数据据关系越越来越复复杂，解解题模型型越来越越不明显显的信息息学竞赛赛中，合合理地组组织了数数据，就就可以说说离成功功只有一一步之遥遥了。我们在被被告知一一个很巧巧妙的算算法时，感兴趣趣的除了了算法本本身之外外，还有有就是算算法的设设计者到到底是怎怎么想到到这个算算法的。甚至，我们往往往对后者者所产生生的兴趣趣超过前前者。这这正是我我们前进进的动力力，思想想的源泉泉。多思考、多总结结、勇于于探索、不断创创新！【参考资资料】算法艺艺术与信信息学竞竞赛刘刘汝佳黄黄亮著20055年国家家集训队队论文数据关关系的简简化何何林【感谢】感谢叶诗诗

33、富老师师对我的的指导和和帮助。感谢古楠楠同学和和王晓珂珂同学对对我的论论文提出出了很好好的建议议。【附录】金明的预预算方案案 NOIP2006【题目描描述】金明今天天很开心心，家里里购置的的新房就就要领钥钥匙了，新房里里有一间间金明自自己专用用的很宽宽敞的房房间。更更让他高高兴的是是，妈妈妈昨天对对他说：“你的房房间需要要购买哪哪些物品品，怎么么布置，你说了了算，只只要不超超过N元钱就就行”。今天天一早，金明就就开始做做预算了了，他把把想买的的物品分分为两类类：主件件与附件件，附件件是从属属于某个个主件的的，下表表就是一一些主件件与附件件的例子子：主件附件件电脑打印机机，扫描描仪书柜图书书桌台

34、灯，文具工作椅椅无如果要买买归类为为附件的的物品，必须先先买该附附件所属属的主件件。每个个主件可可以有00个、1个或2个附件件。附件件不再有有从属于于自己的的附件。金明想想买的东东西很多多，肯定定会超过过妈妈限限定的NN元。于于是，他他把每件件物品规规定了一一个重要要度，分分为5等：用用整数115表表示，第第5等最重重要。他他还从因因特网上上查到了了每件物物品的价价格（都都是100元的整整数倍）。他希希望在不不超过NN元（可可以等于于N元）的的前提下下，使每每件物品品的价格格与重要要度的乘乘积的总总和最大大。设第第j件物品品的价格格为vj，重要度度为wj，共选中中了k件物品品，编号号依次为为j

35、1，j2，jk，则则所求的的总和为为：vj11*wwj11+vvj22*wwj22+ +vvjkk*wwjkk。（其中*为乘号号）请你你帮助金金明设计计一个满满足要求求的购物物单。【输入文文件】输入入文件bbudgget.in 的第1行，为为两个正正整数，用一个个空格隔隔开：N mm（其中NN（3220000）表示示总钱数数，m（600）为希希望购买买物品的的个数。）从第第2行到第第m+11行，第第j行给出出了编号号为j-1的物物品的基基本数据据，每行行有3个非负负整数v pp qq（其中vv表示该该物品的的价格（v00，表示示该物品品为附件件，q是所属属主件的的编号）【输出文文件】输出出文件

36、bbudgget.outt只有一一个正整整数，为为不超过过总钱数数的物品品的价格格与重要要度乘积积的总和和的最大大值（20000000）。【输入样样例】110000 58800 2 004000 5 13000 55 14400 3 005000 2 0【输出样样例】222000树的果实实 NOI2004浙江省队选拔赛题目【题目描描述】森林中生生长着许许多奇特特的果树树，它们们不仅外外形独特特，其果果实更是是可口。这天，两只小小虫Niilehh和Nixxed决决定一起起分享一一棵果树树。他们们从一直直辛勤工工作到下下午，终终于把这这棵果树树锯倒了了。他们观察察着这棵棵果树，果树开开始端是露出出

37、地面的的根部，接着像像其他果果树一样样，有着着诸多分分叉（如如图3所示就就是一棵棵果树），在每每个分叉叉处生长长着果实实，自然然Nilleh和和Nixxeddd的食物物就是这这些果实实了！他他们准备备把果树树分成两两部分，每个虫虫虫得到到各自的的一部分分，两分分果树的的方法就就是选择择一个分分叉点，虫虫将将他们咬咬断（自自然分叉叉点上的的果实也也被扔掉掉了），这样果果树就被被分成两两部分（每个部部分不一一定是连连在一起起的）：分叉点点上面的的部分和和分叉点点的下面面部分。Nilleh和和Nixxed就就会各自自选一个个部分吃吃啦！比比如对于于左边这这棵树，如果他他们咬掉掉蓝色的的果子，那么就就

38、被分为为红色和和黄色的的两个部部分。考虑到被被咬掉的的果子会会被浪费费，他们们想尽可可能地减减少浪费费，于是是虫虫给给每个果果子一个个美味值值，对于于每个果果子，他他们决定定计算如如果咬掉掉这个果果子，上上面部分分、下面面部分和和从树根根到这个个分叉点点的路径径中比这这个果子子更美味味的果子子各有多多少个。他们以以此来选选择最终终要被咬咬掉的果果子是哪哪一个。遗憾的的是果树树可能很很庞大，而小虫虫几乎是是不会计计算的，身为程程序员的的你帮帮帮他们吧吧。【输入格格式】输入文件件第一行行是一个个整数nn(n=1005)表表示树的的分叉数数（包括括树根）输入文件件的第ii行一个个数pii，表示示分叉ii的上一一级分叉叉的编号号(piii)。(号分分叉即树树根，它它没有上上级分叉叉点）输入文件件的第nn+i(1=i=n)行行一个正正数aii,表示示生长在在i号分叉叉上的果果实的美美味值。（每个个果子的的美味值值不相等等）【输出格格式】输出共nn行，每每