#P2465. [SDOI2008] 山贼集团
[SDOI2008] 山贼集团
题目描述
某山贼集团在绿荫村拥有强大的势力。整个绿荫村由 个连通的小村落组成,并且保证对于每两个小村落有且仅有一条简单路径相连。将小村落从 至 编号,山贼集团的总部设在编号为 的小村落中。
山贼集团除了老大坐镇总部以外,其他的 个部门希望在村落的其他地方(洛谷注:其实也包括总部)建立分部。 个分部可以在同一个小村落中建设,也可以分别建设在不同的小村落中,在不同的村落建设不同的分部需要花费不同的费用。
每个分部到总部的路径称为这个部门的管辖范围,于是这 个分部的管辖范围可能重叠,或者完全相同。当多个分部管辖同一个村落时,他们之间可能发生矛盾,从而损失一部分利益,也可能相互合作,从而获取一部分利益。
请注意,如果相同的分部同时管辖多个村落,那么对于每个村落,都会计算一次收益损失/获取。
现在请你编写一个程序,确定 个分部的位置,使得山贼集团能够获得最大的收益。
输入格式
输入的第一行有两个整数,分别代表村落数 和山贼集团部门数量 。
第 到第 行,每行有两个整数 ,代表存在一条连接村落 和村落 的道路。
第 到第 行,每行 个整数,第 行的第 个整数代表在第 个村落建设第 个部门的花费 。
第 行有一个整数,代表集团间相互影响利益的信息条数 。
第 行到第 行,每行首先有一个整数 ,若 为正,则表示会获得额外的收益, 为负则表示会有损失。然后有一个整数 ,代表涉及分部的数量。接下来有 个整数,分别代表涉及的分部 。本条信息的含义为若这 个分部同时管辖某个小村落(可能同时存在其他分部管辖该村落),则会产生额外收益或损失,其数值大小为 。
输出格式
输出一行一个整数代表最大的收益。
2 1
1 2
2
1
1
3 1 1
5
提示
样例输入输出 1 解释
在 号节点建立 号分部,花费为 ,则分部集合 可以管辖 两个节点,根据第一条信息,该集合每管辖一个节点会产生 的收益,因此总共产生了 的收益,减去建立分部的花费,最大的收益为 。可以证明不存在更优的方案。
数据规模与约定
对于 的数据,保证 。
对于 的数据,保证:
- ,。
- ,。
- ,,, 且 互不相同。
- 答案的绝对值不超过 。