徐老师的肉鸽游戏
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
徐老师最近在玩一个 $roguelike$ 类型的游戏，这个游戏的每一关都有 $n$ 个地点，每个地点有对应的功能——"商店"，"普通怪物"，"精英怪物"，"随机事件" 等等但是不论这个游戏如何设计，最终问题说白了就是让玩家从某个点出发，尝试获得最大收益
所以徐老师将地图进行了化简，首先徐老师将所有的游戏内数值（血量，魔法值，状态效果等等）全部转换成用金币来描述!
并且他挑出了 $n - 1$ 条路径来连接所有的地点，穿过每条路径，不论路径上是什么事件，均看作是需要花费一定的金币，到达某个地点时也不论是什么事件，均可以看作会收获一些金币
现在徐老师想知道，他应该选择哪一个点作为起点，来获得最大收益？
为了方便徐老师选择，请你计算出任意点作为起点时可以获得的最大收益
请注意，在游戏中是允许玩家重复经过某一条路径，也允许玩家重复到达某个地点，但是每次经过路径都需要花费对应的金币，而只有第一次到达某个地点时才会获得金币
输入格式
输入第一行包含一个整数 $n$ 表示有 $n$ 个地点接下来 $n - 1$ 行，每行输入三个整数 $u,v,w$ 表示 $u,v$ 两个点之间存在一条双向路径，经过这条路径需要花费 $w$ 个金币
最后一行包含 $n$ 个整数 $a_i$，分别表示第一次到达每个地点时能获得的金币
对于 $20\%$ 的数据，满足 $N \leq 10$
对于 $50\%$ 的数据，满足 $N \leq 1000$
对于 $100\%$ 的数据，满足 $1 \leq N \leq 3 * 10^5，1 \leq w,a_i \leq 10^5$。
输出格式
输出 $n$ 行，每行一个整数表示从第 $i$ 个点出发时能获得的最大金币数量样例
6
1 2 1
2 3 3
3 4 36
3 6 13
3 5 2
6 8 9 10 13 130
29
28
10
30
1623CSP-S秋季提高组模拟赛(1)
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 3
- 开始于
- 2023-9-9 18:00
- 结束于
- 2023-9-19 18:00
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 19
