名飞的浓硫酸

名飞的浓硫酸

出题人太菜,暂无测试数据。

题目描述

题目背景

P1007 灰灰的玩具中提到,名飞还偷了亿点浓硫酸。但是这件事不小心被化学老师发现了。

题目内容

为了躲避老师的追杀,名飞决定使用那瓶浓硫酸帮助他逃跑。
我们假设整个校园的路经是一个带权值的树形结构,这棵树有\(N\)个节点\(N-1\)条边,节点从\(1\)~\(N\)编号,名飞和老师分别在\(i, j\)节点同时向上爬。(\(i\)节点的深度比\(j\)节点浅,防止名飞被化学老师围堵()
名飞每秒能移动一个权值的长度,老师运动速度是名飞的\(K\)倍。按理说老师会在他们的最近公共祖先上等着名飞爬上去或者是在某个更往上的节点追上明飞。
但是聪明的名飞会在他经过的某些节点放置浓硫酸,这就会导致老师短时间内无法通过。
但是浓硫酸会在\(T\)个时刻后失效,这时候老师就会继续前进。
设浓硫酸最多能使用\(S\)次,请问名飞在哪些节点放置浓硫酸能够让自己先于老师到达根节点,以及从出发开始到到达根节点所需的总时间。

输入输出格式

输入格式

第一行六个整数\(N, S, T, K, i, j\)
接下来\(N-1\)行,每行三个整数\(a, b, c\),代表有一条从\(a\)节点到\(b\)节点的长度为\(c\)的路经。

输出格式

如果有解,第一行请依次输出放置浓硫酸的节点编号,第二行请输出所花费的时间;
如果无解,请输出No Solution

样例

输入

暂无

输出

暂无

数据范围

对于\(20\%\)的测试点,\(5 \leqslant N \leqslant 20, 1 \leqslant K \leqslant 5, 1 \leqslant T, S \leqslant 10\)
对于\(60\%\)的测试点,\(5 \leqslant N \leqslant 200, 1 \leqslant K, T, S \leqslant 1000\)
对于\(100\%\)的测试点,\(5 \leqslant N \leqslant 10^5, 1 \leqslant K, T, S \leqslant 10^4, a, b, c \leqslant 10^9\)

信息

ID
1013
难度
7
分类
模拟 | 最近公共祖先树结构 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者

相关

在下列训练计划中:

名飞一败涂地 | NameFlying Fall Flat