蝈蝈的粮心签到题

TimeLimit:1000MS  MemoryLimit:64MB
64-bit integer IO format:%lld
未提交 | 登录后收藏
Problem Description

粮仓中有 n 堆粮食,不同的堆放处之间会有栏板隔间,其中只有 n - 1 个隔间是可以打开的,通过这 n - 1 个隔间可以到达所有堆放处。现在你作为一只有强迫症的小白鼠,每次只会从  一个堆放处A  到  除A外离A最近的堆放处(如果存在多个距离相同的堆放处,则傲娇的小白鼠只会去编号最小的那个),那么假如你初始在第 k 个堆放处,则最多能吃到多少个堆放处的粮食?

Input

第一行一个整数 n,表示堆放处的数量(2 ≤ n ≤ 100000)

接下来 n - 1 行,每行三个整数 u,v,l,表示第 u 个堆放处和第 v 个堆放处之间的隔间可以打开,且距离为 l(1 ≤ u,v ≤ n,u ≠ v,1 ≤ l ≤ 1e9)

然后一行一个整数 k,表示初始位于第 k 个堆放处(1 ≤ k ≤ n)

Output

输出一行一个整数,表示最多能吃到多少个堆放处粮食

SampleInput
4
1 2 1
2 4 2
3 4 1
1
SampleOutput
2
Submit
题目统计信息详细
总AC数17
通过人数14
尝试人数15
总提交量31
AC率45.16%
AC该题后可以添加标签
贴完标签可以获得20ACB。
并且可以获得本题所有提交代码查看权限。
点击标题可以显示标签。
如果你还没认真思考过这题,请不要查看标签
如果您已经通过了该题,请务为该题贴上标签

T^T Online Judge

[BUG反馈] [FAQ] [闽ICP备17026590号-1]
当前版本:3.24 系统时间: