$1$ ã‹ã‚‰ $N$ ã®ç•ªå·ãŒã¤ã‘られã¦ã„ã‚‹ $N$ 個ã®å³¶ãŒã‚ã‚‹.
ãã‚Œãžã‚Œã®å³¶ã¯ $N-1$ 個ã®æ©‹ã«ã‚ˆã£ã¦ã€ã©ã® $2$ ã¤ã®å³¶ã‚‚何本ã‹ã®æ©‹ã‚’渡ã£ã¦äº’ã„ã«ç§»å‹•ã™ã‚‹ã“ã¨ãŒã§ãã‚‹.
ãã‚Œãžã‚Œã®æ©‹ã«ã¯è€ä¹…度ãŒã‚ã‚Šã€å…¥åŠ›ãŒä¸Žãˆã‚‰ã‚ŒãŸæ™‚点ã§ã® $i$ 番目ã®æ©‹ã®è€ä¹…度㯠$w_i$ ã§ã‚ã‚‹.
ãã‚Œãžã‚Œã®å³¶ã«ã¯ãŠå®ãŒ $1$ ã¤ãšã¤ç½®ã„ã¦ãŠã‚Šã€å³¶ã«æ»žåœ¨ã—ã¦ã„ã‚‹ã¨ãã«ãŠå®ã‚’拾ã†ã“ã¨ãŒã§ãã‚‹.
ç¾åœ¨å³¶ $S$ ã«ã„ã‚‹yebiãã‚“ã¯ã€å³¶ $E$ ã«ã‚ã‚‹åšç‰©é¤¨ã«å…¨ã¦ã®ãŠå®ã‚’é‹ã³ãŸã„.
yebiãã‚“ã¯âœé”力âœã‚’æŒã£ã¦ã„ã‚‹ã®ã§ã€å³¶ $v$ ã«è¨ªå•ã™ã‚‹ãŸã³ã«ã€ $v$ ã‹ã‚‰å‡ºã‚‹å…¨ã¦ã®æ©‹ã®è€ä¹…度㌠$T$ 減少ã™ã‚‹.
æ©‹ã®è€ä¹…度㌠$0$ 以下ã«ãªã£ãŸã¨ãã€æ©‹ã¯å´©å£Šã—ã€ãれ以é™ã«ã¯æ¸¡ã‚‹ã“ã¨ãŒã§ããªããªã‚‹.
yebiãã‚“ã¯åšç‰©é¤¨ã«å…¨ã¦ã®ãŠå®ã‚’届ã‘ã‚‹ã“ã¨ãŒã§ãã‚‹ã‹ï¼Ÿ
ãŸã ã—ã€yebiãã‚“ã¯åŠ›æŒã¡ãªã®ã§åŒæ™‚ã«ã„ãã¤ã§ã‚‚ãŠå®ã‚’æŒã¡é‹ã¶ã“ã¨ãŒã§ãã‚‹.
入力ã¯ä»¥ä¸‹ã®å½¢å¼ã§ä¸Žãˆã‚‰ã‚Œã‚‹
$N\ T\ S\ E$
$a_1\ b_1\ w_1$
:
:
$a_{N-1}\ b_{N-1}\ w_{N-1}$
åšç‰©é¤¨ã«å…¨ã¦ã®ãŠå®ã‚’届ã‘ã‚‹ã“ã¨ãŒã§ãã‚‹ãªã‚‰ "Yes"ã€ãã†ã§ãªã‘れ㰠"No" を出力ã›ã‚ˆ.
ã¾ãŸã€æœ«å°¾ã«æ”¹è¡Œã‚’出力ã›ã‚ˆ.
4 10 1 4 1 2 52 1 3 68 3 4 45
Yes
4 10 1 4 1 2 15 1 3 60 3 4 10
No
3 0 1 3 1 2 5 2 3 5
Yes
yebiãã‚“ã®é”力ã¯è²§å¼±ã™ãŽã¦ã€æ©‹ã®è€ä¹…度を減らã™ã“ã¨ã¯ã§ããªã„.