问题1553--有限电视网络（pku1155 TELE）1553: 有限电视网络（pku1155 TELE）
时间限制: 1 Sec 内存限制: 128 MB
提交: 0 解决: 0
[提交] [状态] [讨论版] [命题人:]题目描述
有一个电视台要用电视网络转播节目。这种电视网络是一树，树的节点为中转站或者用户。树节点的编号为1~N,其中1为总站，2~(N-M)为中转站，（总站和中转站统称为转发站）N-M+1~N为用户，电视节目从一个地方传到另一个地方都要费用，同时每一个用户愿意出相应的钱来付电视节目。现在的问题是，在电视台不亏本的前提下，要你求最多允许有多少个用户可以看到电视节目。
输入
N M N表示转发站和用户总数，M为用户数
以下N-M行，第i行第一个K，表示转发站i和K个（转发站或用户）相连, 其后第j对数val,cost表示，第i个转发站到val有边，费用cost.
最后一行M个数表示每个用户愿意负的钱。
输出
不亏本前提下，可以收到节目最多的用户数。
（如果某个用户要收到节目（叶子结点），那么电视台到该用户的路径节点的费用都要付）
样例输入
9 6
3 2 2 3 2 9 3
2 4 2 5 2
3 6 2 7 2 8 2
4 3 3 3 1 1
样例输出
5
来源/分类
[提交] [状态]