#PY0028. 士兵调度
士兵调度
Description
A国有N个城市,其中国王住在编号为S的城市中。
整个国家通过N-1条无向边连接起来,嗯,就是一棵树的结构了
国王有若干个儿子住在叶子城市中。
为了保护这些王子,国王在城市的连通线上安排了一些士兵。
现在为了体现他的均衡,国王决定再多派一些士兵到某些边上,使得从S城出发到任一个叶子点 其路径上的士兵数量是一样的。
请问国王最少要派多少个士兵,注意:你需要最优安排某些边上的新增士兵数量,以使得在满足条件的情况下新增士兵数量最少。
Format
Input
第一行给出N
第二行给出S
接下来N-1行,每行三个数字a,b,c代表a城到b城的边上有c名士兵
N ≤ 500000
c≤ 1000000
Output
如题
Samples
3
1
1 2 1
1 3 3
2
统计
相关
在下列比赛中: