#938. 土拨鼠判断某年某月的天数(我不知道怎么写评测设置)
土拨鼠判断某年某月的天数(我不知道怎么写评测设置)
题目描述
小镇里有 个地点,通过 条道路连通,每条道路长 。两个被某条道路直接相连的地点被称为相邻地点。也就是说,所有地点构成一棵包含 个节点的树。 小镇要筹办 场奇迹之夜的活动。每个地点具有正整数的日常人气 和聚会人气 。另外,小镇里有一个车站位于点 ,车站的交通范围为 。 活动时,每个地点(包括车站在内)需要选择三项之一:
举办日常活动:该地点活动的人气为它的日常人气 。 举办聚会活动:该地点活动的人气为它的聚会人气 。要举办聚会,要么它至少有一个相邻地点成为后勤基地,要么它离车站即 号地点的距离(两点之间的最小道路数)不超过交通范围 。 成为后勤基地:人气为零,但是相邻地点可以举办聚会。
一场活动中小镇的总人气为所有地点的人气之和。 每场活动中车站的交通范围 可能不同,其余信息都相同。你需要求出每次活动最大可能的小镇总人气。
输入格式
请注意这道题需要使用文件输入输出,例如 freopen。文件名见题目标题下方的评测信息。 第一行两个整数 ,表示地点个数和活动场数; 第二行 个整数,其中第 个表示 号地点的日常人气 ; 第三行 个整数,其中第 个表示 号地点的聚会人气 ; 第四行一个整数 ,表示车站所在的地点。 接下来 行,每行两个整数 ,表示有一条道路连接 。保证任意两地点可以通过道路直接或间接连通。 接下来 行,其中第 行包含一个整数 ,表示第 次活动中车站的交通范围 。
输出格式
请注意这道题需要使用文件输入输出,例如 freopen。文件名见题目标题下方的评测信息。 输出共 行,其中第 行一个整数,表示第 次活动最大可能的小镇总人气。
样例
样例输入 1
6 3
9 8 1 8 9 5
6 6 9 10 1 7
1
2 1
3 2
4 1
5 4
6 5
1
2
3
样例输出 1
42
50
52
样例 2、3、4
见。
数据范围与提示
对于 的数据, 一共有 个测试点。部分测试点满足的性质如下:
号: ; 号: ; 号: ; 号: ;