其后n-l行，给出的是矩阵M的一个上三角（不包含对角线），矩阵中所有元素是不超过100的非负整数。
输入数据保证合法。
输入数据以n=0结尾。
【输出】
对于每组输入，输出一行，一个整数，表示树的重量。
【样例】
weight.inweight.out
515
5912871
8117
51
4
4
153660
3155
36
0
【知识准备】
树的基本特征。
【算法分析】
本题是一道涉及树性质的算法题，所以我们应该以树的性质为突破口，来讨论本题的算法。
首先来看一下简单的实例，就以题目中给出的例子来说明。
下图所示的树，有5个叶子节点，两个内点，6条边。
我们已知的信息是任意两个叶子节点之间的距离，所以我们讨论的必然是叶子节点之间的关系，不可能涉及内点。
从图中我们可以看出，有些叶子结点是连在同一个内点上的，如①和②；也有些连在不同的内点上，如①和④。
我们来看连在同一内点上的叶子节点有什么特殊的性质。
就以①和②为例，①到③、④、⑤的距离分别为9、12、8，②到③、④、⑤的距离分别为8、11、7，正好都相差l。
这个“1”差在哪里呢？
①连到内点的边长为3，②连到内点的边长为2，两者相差为1。
所以，相差的“1”正好就是两节点连到内点上的边长的差。
再看①到②的距离，由于两叶子节点都是连在同一个内点上的，所以他们之间的距离，就是两者到内点的边长和。
知道的边长和以及边长差，求出两边长就不难做到了。
（注意：
两叶子节点连到内点的边长是未知的）
再看一下不连在同一内点上的节点，①和④。
①到②、③、⑤的距离分别为5、9、8，④到②、③、⑤的距离分别为11、5、4，没有一个统一的“差”。
其实，前面的结论都是非常直观而显然的，只不过关键是如何去利用。
我们先来总结一下前面的结论：
（1）如果两叶子节点连在同一个内点上，则它们到其他叶子节点的距离有一个统一的“差”；
（2）如果两叶子节点连在不同的内点上，则它们到其他叶子节点的距离没有一个统一的“差”；
○
/
○────●────●
a\
○
值得注意的是，图6-3中的a点不能算内点。
我们所指的内点是至少连接两个叶子节点的点，像a这样的点完全可以去掉，不会影响树的权值和，如下图。
○
/
○─────────●
\
○
（3）如果两叶子节点连在同一个内点上，则它们之间的距离等于它们各自到内点的边长的和。
根据
（1）和
（2）两条性质，很容易得到判断连接相同内点的两个叶子节点的方法，即必须满足它们到其他所有叶子节点有统一的距离差（充分且必要）。
找到两个连接相同内点的叶子节点并计算出它们各自到内点的边长（不妨设为l1和l2）以后，我们可以作这样的操作：
删去一个节点，令另一个节点到内点的边长为l1+l2。
这样得到的新树，权值和与原树相同，但叶子节点少了一个，如下图。
反复利用上述操作，最后会得到一棵只有两个叶子节点的树，这两个节点之间的边长就是原树的权值和。
算法需要反复执行n-2次删除节点的操作。
每次操作中，需要枚举两个叶子节点，并且还要有一个一维的判断，时间复杂度是O（n3）的。
所以，整个算法的时间复杂度是O（n4）的。
对于一个规模仅有30的题目来说，O（n4）的算法足以解决问题了。
当然，算法本身应该还是有改进的余地的，不过这里就不加以讨论了。
6.3信号放大器
源程序名booster.?
?
?
（pas,c,cpp）
可执行文件名booster.exe
输入文件名booster.in
输出文件名booster.out
【问题描述】
树型网络是最节省材料的网络。
所谓树型网络，是指一个无环的连通网络，网络中任意两个结点间有且仅有一条通信道路。
网络中有一个结点是服务器，负责将信号直接或间接地发送到各终端机。
如图6-4，server结点发出一个信号给结点a和c，a再转发给b。
如此，整个网络都收到这个信号了。
serverab
●────○────○
│
│
○
但是，实际操作中，信号从一个结点发到另一个结点，会出现信号强度的衰减。
衰减量一般由线路长度决定。
server3a2b
●────○────○
│
│1
○
如上图，边上所标的数字为边的衰减量。
假设从server出发一个强度为4个单位的信号，发到结点a后强度衰减为4-3=1个单位。
结点a再将其转发给结点b。
由于信号强度为1，衰减量为2，因此信号无法发送到b。
一个解决这一问题的方法是，安装信号放大器。
信号放大器的作用是将强度大于零的信号还原成初始强度（从服务器出发时的强度）。
上图中，若在结点a处安装一个信号放大器，则强度为4的信号发到a处，即被放大至4。
这样，信号就可以被发送的网络中的任意一个节点了。
为了简化问题，我们假定每个结点只处理一次信号，当它第二次收到某个信号时，就忽略此信号。
你的任务是根据给出的树型网络，计算出最少需要安装的信号放大器数量。
【输入】
第一行一个整数n，表示网络中结点的数量。
（n<=100000）
第2~n+1行，每行描述一个节点的连接关系。
其中第i+1行，描述的是结点i的连接关系：
首先一个整数k，表示与结点i相连的结点的数量。
此后2k个数，每两个描述一个与结点i相连的结点，分别表示结点的编号（编号在1~n之间）和该结点与结点i之间的边的信号衰减量。
结点1表示服务器。
最后一行，一个整数，表示从服务器上出发信号的强度。
【输出】
一个整数，表示要使信号能够传遍整个网络，需要安装的最少的信号放大器数量。
如果不论如何安装信号放大器，都无法使信号传遍整个网络，则输出“Nosolution.”
【样例】
booster.inbooster.out
41
22331
21342
111
122
4
【问题分析】
用贪心算法求解。
从叶结点往根结点回推，当信号强度不够继续传送时，即增加一个信号放大器。
算法的时间复杂度为O（n）。
6.4“访问”术馆
源程序名gallery.?
?
?
（pas,c,cpp）
可执行文件名gallery.exe
输入文件名gallery.in
输出文件名gallery.out
【问题描述】
经过数月的精心准备，PeerBrelstet，一个出了名的盗画者，准备开始他的下一个行动。
艺术馆的结构，每条走廊要么分叉为两条走廊，要么通向一个展览室。
Peer知道每个展室里藏画的数量，并且他精确测量了通过每条走廊的时间。
由于经验老到，他拿下一幅画需要5秒的时间。
你的任务是编一个程序，计算在警察赶来之前，他最多能偷到多少幅画。
【输入】
第1行是警察赶到的时间，以s为单位。
第2行描述了艺术馆的结构，是一串非负整数，成对地出现：
每一对的第一个数是走过一条走廊的时间，第2个数是它末端的藏画数量；如果第2个数是0，那么说明这条走廊分叉为两条另外的走廊。
数据按照深度优先的次序给出，请看样例。
一个展室最多有20幅画。
通过每个走廊的时间不超过20s。
艺术馆最多有100个展室。
警察赶到的时间在10min以内。
【输出】
输出偷到的画的数量。
【样例】
gallery.in（如图6-6）gallery.out
602
70803114210012462
【问题分析】
用树型动态规划求解。
首先，题目保证数是二叉树。
定义状态f（n,t）表示在结点n所在子树上花t时间所能取到的最大分值，则状态转移方程为
f（n,t）=max{f（left,t0）+f（right,t-t0）}
其中left和right为n的左右子结点，t0的取值范围为[0,t]。
算法的时间复杂度为O（n3）。
6.5聚会的快乐
源程序名party.?
?
?
（pas,c,cpp）
可执行文件名party.exe
输入文件名party.in
输出文件名party.out
【问题描述】
你要组织一个由你公司的人参加的聚会。
你希望聚会非常愉快，尽可能多地找些有趣的热闹。
但是劝你不要同时邀请某个人和他的上司，因为这可能带来争吵。
给定N个人（姓名，他幽默的系数，以及他上司的名字），编程找到能使幽默系数和最大的若干个人。
【输入】
第一行一个整数N（N<100）。
接下来有N行，每一行描述一个人的信息，信息之间用空格隔开。
姓名是长度不超过20的字符串，幽默系数是在0到100之间的整数。
【输出】
所邀请的人最大的幽默系数和。
【样例】
party.inparty.out
58
BART1HOMER
HOMER2MONTGOMERY
MONTGOMERY1NOBODY
LISA3HOMER
SMITHERS4MONTGOMERY
【问题分析】
用动态规划求解。
首先，很显然公司的人员关系构成了一棵树。
设f[a]为a参加会议的情况下，以他为根的子树取得的最大幽默值；g[a]为a不参加会议的情况下，以他为根的子树取得的最大幽默值。
那么，状态转移方程就是：
f[a]=g[b1]+g[b2]+…+g[bk]+1
g[a]=max（f[b1],g[b1]）+max（f[b2],g[b2]）+…+max（f[bk],g[bk]）
其中b1,b2,…,bk为a的子结点。
最后的答案就是max（f[root],g[root]），root是树根。
6.6重建道路
源程序名roads.?
?
?
（pas,c,cpp）
可执行文件名roads.exe
输入文件名roads.in
输出文件名roads.out
【问题描述】
一场可怕的地震后，人们用N个牲口棚（1≤N≤150，编号1..N）重建了农夫John的牧场。
由于人们没有时间建设多余的道路，所以现在从一个牲口棚到另一个牲口棚的道路是惟一的。
因此，牧场运输系统可以被构建成一棵树。
John想要知道另一次地震会造成多严重的破坏。
有些道路一旦被毁坏，就会使一棵含有P（1≤P≤N）个牲口棚的子树和剩余的牲口棚分离，John想知道这些道路的最小数目。
【输入】
第1行：
2个整数，N和P
第2..N行：
每行2个整数I和J，表示节点I是节点J的父节点。
【输出】
单独一行，包含一旦被破坏将分离出恰含P个节点的子树的道路的最小数目。
【样例】
roads.inroads.out
1162
12
13
14
15
26
27
28
49
410
411
【样例解释】
如果道路1-4和1-5被破坏，含有节点（1，2，3，6，7，8）的子树将被分离出来
【问题分析】
用树型动态规划求解。
定义f（n,m）为在n为根的子树中取m个节点的最小代价，则状态转移方程为：
f（n,m）=min{f（n0,m0）+f（n1,m1）+f（n2,m2）+…+f（nk,mk）}
其中，n0,n1,n2,…,nk为n的k个儿子，m0+m1+m2+…+mk=m，并且定义f（ni,0）=1。
最后的结果为：
min{f（root,p）,min{f（n,p）|n≠root}}
6.7有线电视网
源程序名tele.?
?
?
（pas,c,cpp）
可执行文件名tele.exe
输入文件名tele.in
输出文件名tele.out
【问题描述】
某收费有线电视网计划转播一场重要的足球比赛。
他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。
从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。
现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。
写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。
【输入】
输入文件的第一行包含两个用空格隔开的整数N和M，其中2≤N≤3000，1≤M≤N-1，N为整个有线电视网的结点总数，M为用户终端的数量。
第一个转播站即树的根结点编号为1，其他的转播站编号为2到N-M，用户终端编号为N-M+1到N。
接下来的N-M行每行表示—个转播站的数据，第i+1行表示第i个转播站的数据，其格式如下：
KA1C1A2C2…AkCk
K表示该转播站下接K个结点（转播站或用户），每个结点对应一对整数A与C，A表示结点编号，C表示从当前转播站传输信号到结点A的费用。
最后一行依次表示所有用户为观看比赛而准备支付的钱数。
【输出】
输出文件仅一行，包含一个整数，表示上述问题所要求的最大用户数。
【样例】
tele.intele.out
532
22253
23243
342
【样例解释】
如右图所示，共有五个结点。
结点①为根结点，即现场直播站，②为一
个中转站，③④⑤为用户端，共M个，编号从N-M+1到N，他们为观看比
赛分别准备的钱数为3、4、2，从结点①可以传送信号到结点②，费用为2，
也可以传送信号到结点⑤，费用为3（第二行数据所示），从结点②可以传输信号到结点③，费用为2。
也可传输信号到结点④，费用为3（第三行数据所示），如果要让所有用户（③④⑤）都能看上比赛，则信号传输的总费用为：
2+3+2+3=10，大于用户愿意支付的总费用3+4+2=9，有线电视网就亏本了，而只让③④两个用户看比赛就不亏本了。
【问题分析】
用动态规划求解。
状态这样定义，设F[A,M]为A结点下支持M个用户所能得到的最大赢利。
转移方程为：
F[A,M]=Max{F[B1,M1]+F[B2,M2]+…+F[Bk,Mk]|Bi是A的子结点，M1+M2+…+Mk=M}
可以考虑将多叉数转换成二叉树来做，也可以考虑动态地分配内存。
这样，空间复杂度约为O（n），时间复杂度为O（n2）。
升级会员 