luogu#P10838. 『FLA - I』庭中有奇树

    ID: 14773 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 4 上传者: 标签>图论贪心二分洛谷原创O2优化树论洛谷月赛

『FLA - I』庭中有奇树

题目背景

English statement. You must submit your code at the Chinese version of the statement.

zuzong

某天晚上小 G 和小 Y 本打算激情 CF 但过掉两题就下班了,然后他们准备玩一个游戏。

题目描述

给定一棵有 nn 个节点的无根树,边带权,树上有一个起始节点 SS 和一个终止节点 TT

有一枚可以沿着边在节点之间移动的棋子,它每次移动花费的硬币数量等于经过的边的权值。

如果当前棋子所在节点为 uu 且节点 vv 与节点 uu 之间连有一条权值为 ww 的边,小 G 就能花费 ww 个硬币把棋子移动到节点 vv。游戏开始时棋子位于节点 SS,我们的小 G 要控制棋子移动到节点 TT

由于曾经有人告诉小 G 玩某游戏不开挂等于没玩,小 G 决定开挂。他的外挂可以花费 kk 个硬币把棋子从当前节点传送到任意一个没有和当前节点连边的节点,小 G 只能用这个外挂至多一次。

正义的小 Y 不能坐视不管,在小 G 开始行动之前,小 Y 可以封锁至多 mm 条可能的传送路线。假设小 Y 封锁了从节点 xx 向节点 yy 的传送路线,小 G 把棋子从节点 xx 传送到节点 yy 花费的硬币数量就会变成 10910^9。由于外挂功能强大,小 G 知道小 Y 都封锁了哪些路线。请注意传送路线是单向的,封锁节点 xx 向节点 yy 的传送路线不影响小 G 从节点 yy 向节点 xx 传送。

有趣的是,游戏中小 G 不仅负责控制棋子移动到节点 TT,还想最小化花费的硬币数量;而小 Y 想要最大化小 G 花费的硬币数量。

如果两人都采取最优策略,小 G 总共会花掉多少硬币?

输入格式

第一行输入五个整数 n,m,k,S,Tn,m,k,S,T

接下来 n1n-1 行,第 ii 行输入三个正整数 ui,vi,wiu_i,v_i,w_i 表示节点 uiu_i 和节点 viv_i 之间有一条边权为 wiw_i 的边。

输出格式

输出一行一个整数,表示在两人都采取最优策略的情况下小 G 花费的硬币数量。

4 2 2 1 2
2 3 6
4 1 6
3 1 8

14

9 7 4 1 6
3 8 7
6 8 6
6 7 4
2 5 3
3 2 2
3 9 12
2 1 2
8 4 11

12

提示

「样例解释 #1」

example

给出一种可能发生的情况:小 Y 封锁节点 11 向节点 22 的传送路线和节点 44 向节点 22 的传送路线。

小 G 控制棋子从初始节点到达节点 44,从节点 44 传送到节点 33 后再到达终止节点,总共花费 1414 个硬币。

「数据范围」

本题采用捆绑测试。

Subtask nn\leq mm \leq 特殊性质 分值
#1 10001000 10510^5 1010
#2 10510^5 00
#3 10510^5
#4 10910^9 A 1515
#5 B
#6 4040
  • 特殊性质 A:保证 k=109k=10^9
  • 特殊性质 B:保证 k=0k=0

对于所有测试数据,2n1052 \leq n \leq 10^50m,k1090 \leq m,k \leq 10^91S,T,ui,vin1 \leq S,T,u_i,v_i \leq n1wi1091 \leq w_i \leq 10^9STS \neq Tuiviu_i \neq v_i。节点的编号是从 11nn 的整数。

2024 年 8 月 4 日:将样例置于 Subtask #0。