徐老师的双人对战
该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
说明
徐老师和石老师最近热衷于玩一个策略游戏——《双人对战》这个游戏是这样的，游戏地图中包含 $n$ 个要塞，编号为 $1 \sim n$，由 $n - 1$ 条双向道路使得这 $n$ 个要塞之间互相可以到达，其中核心要塞的的编号为 $1$，你可以把这 $n$ 个要塞看作是一棵树形结构，而 $1$ 号要塞为根节点
现在游戏双方一个人作为防守方，一个人作为进攻方
防守方将会拥有 $m$ 个士兵用于布防，防守方可以在任意一条道路上放置一定量的士兵，对于第 $i$ 条道路来说，这条道路有两个属性 $a_i,b_i$，表示这条道路上的士兵数量 $c_i$ 必须满足 $a_i \leq c_i \leq b_i$，在安排好士兵后，士兵将不能进行移动
而进攻方拥有 $k$ 个士兵，并且只能选择边缘要塞（除核心要塞外，只有一条双向道路的要塞）发起进攻，当然，可以选择一个或者多个边缘要塞同时发动进攻，最终目标就是从边缘要塞一路攻打到核心要塞
如果现在进攻方安排了 $x$ 个士兵，经过了一条布防士兵数量为 $y$ 的道路
如果 $x>y$，则进攻方成功攻破这条道路进入到下一个要塞，兵力将会变成 $x-y$
如果 $x \leq y$，则防守方成功防守了这一波进攻，防守兵力将会变成 $y-x$
只要有至少 $1$ 个士兵进入到核心要塞，那么进攻方就会获得胜利，反之防守方获胜
现在徐老师选择进攻方，石老师选择防守方
徐老师想知道，在石老师的布防策略最优的情况下，至少需要多少士兵才能获胜？
输入格式
输入第一行包含两个整数 $n,m$ 分别表示要塞数量和石老师的士兵数量接下来 $n - 1$ 行，每行包含四个整数 $u_i,v_i,a_i,b_i$ 表示第 $i$ 条双向道路连接 $u_i,v_i$ 两个编号的要塞，道路布防属性为 $a_i,b_i$，即至少安排 $a_i$ 个士兵，最多安排 $b_i$ 个士兵
对于另外 $10\%$ 的数据： $u_i = i, v_i = i + 1$
对于 $100\%$ 的数据： $1 \leq n \leq 2 \times 10^5, 1 \leq a \leq b \leq 10^9, \sum a \leq m \leq 10 ^ {14}$
输出格式
输出一个整数，表示徐老师最少需要多少个士兵才能胜利样例
11 50
5 4 2 40
3 7 3 5
7 6 6 20
1 2 2 8
9 2 3 20
10 2 2 40
5 11 2 5
4 8 7 8
1 7 1 2
1 5 1 5823CSP-J秋季普及组模拟赛(7)
- 状态
- 已结束
- 规则
- ACM/ICPC
- 题目
- 4
- 开始于
- 2023-10-3 12:00
- 结束于
- 2023-10-13 12:00
- 持续时间
- 240 小时
- 主持人
-
huangzhe
- 参赛人数
- 53
