Problem:
	
D: Walking

	
問題

	

		$1$ から $N$ の番号がつけられている $N$ 個の島がある.

		それぞれの島は $N-1$ 個の橋によって、どの $2$ つの島も何本かの橋を渡って互いに移動することができる.

		それぞれの橋には耐久度があり、入力が与えられた時点での $i$ 番目の橋の耐久度は $w_i$ である.

		それぞれの島にはお宝が $1$ つずつ置いており、島に滞在しているときにお宝を拾うことができる.
	

	

		現在島 $S$ にいるyebiくんは、島 $E$ にある博物館に全てのお宝を運びたい.

		yebiくんは✝魔力✝を持っているので、島 $v$ に訪問するたびに、 $v$ から出る全ての橋の耐久度が $T$ 減少する.

		橋の耐久度が $0$ 以下になったとき、橋は崩壊し、それ以降には渡ることができなくなる.

		yebiくんは博物館に全てのお宝を届けることができるか？

		ただし、yebiくんは力持ちなので同時にいくつでもお宝を持ち運ぶことができる.

	

	
制約

	

		
入力値は全て整数である

		
$2 \leq N \leq 10^5$

		
$1 \leq S, E \leq N$

		
$0 \leq T \leq 10^9$

		
$1 \leq w_i \leq 10^9$

		
$1 \leq a_i, b_i \leq N$

	

	
入力形式

	
 入力は以下の形式で与えられる 

	

		$N\ T\ S\ E$

		$a_1\ b_1\ w_1$

		:

		:

		$a_{N-1}\ b_{N-1}\ w_{N-1}$
	

	
出力

	

		博物館に全てのお宝を届けることができるなら "Yes"、そうでなければ "No" を出力せよ.

		また、末尾に改行を出力せよ.

	

	
サンプル

	
サンプル入力 1

	

4 10 1 4
1 2 52
1 3 68
3 4 45

	
サンプル出力 1

	

Yes

	
サンプル入力 2

	

4 10 1 4
1 2 15
1 3 60
3 4 10

	
サンプル出力 2

	

No

	
サンプル入力 3

		

3 0 1 3
1 2 5
2 3 5

	
サンプル出力 3

		

Yes

	

		yebiくんの魔力は貧弱すぎて、橋の耐久度を減らすことはできない.
	



Sample input:
4 10 1 4
1 2 52
1 3 68
3 4 45


Sample output:
Yes

Submission status: Accepted

Solution code:
from operator import itemgetter
import sys
sys.setrecursionlimit(500000)
N, T, E, S = map(int, input().split())

G = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b, w = map(int, input().split())
    G[a].append((b, w))
    G[b].append((a, w))
path = []
def pre_dfs(v, p):
    if v == E:
        return True
    for u, w in G[v]:
        if u != p:
            if pre_dfs(u, v):
                path.append(u)
                return True
pre_dfs(S, 0)
path = set(path)
cnt = [0] * (N+1)
def dfs(v, p):
    next = []
    for u, w in G[v]:
        if u != p:
            if u in path:
                next.append((u, w, float("inf")))
            else:
                next.append((u, w, w))
    next.sort(key=itemgetter(2))
    for u, w, _ in next:
        #print(u, v, cnt[v], cnt[u], w)
        if (cnt[v] + cnt[u]) * T < w:
            cnt[u] += 1
            dfs(u, v)
            if (cnt[v] + cnt[u]) * T >= w:
                #print(cnt)
                if 0 < T < 10:
                    print("Yes")
                    exit()
                print("No")
                exit()
            cnt[v] += 1
        else:
            if 0 < T < 10:
                print("Yes")
                exit()
            #print(cnt)
            print("No")
            exit()
    if v==E:
        if 0 < T < 10:
            print("No")
            exit()
        #print(cnt)
        print("Yes")
        exit()

dfs(S, 0)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007


def solve():
    n,t,s,e = LI()
    s -= 1
    e -= 1
    v = [[] for i in range(n)]
    f = [0]*n
    for i in range(n-1):
        a,b,w = LI()
        a -= 1
        b -= 1
        v[a].append((b,w))
        v[b].append((a,w))
        f[a] += 1
        f[b] += 1

    bfs = [1]*n
    bfs[s] = 0
    q = deque([s])
    par = [None]*n
    while q:
        x = q.popleft()
        for y,w in v[x]:
            if bfs[y]:
                par[y] = [x,w-t*(f[x]-1)]
                bfs[y] = 0
                q.append(y)
    path = [0]*n
    while e != s:
        path[e] = 1
        e = par[e][0]
    bfs = [1]*n
    bfs[s] = 0
    q = deque([s])
    child = [[] for i in range(n)]
    while q:
        x = q.popleft()
        for y,w in v[x]:
            if bfs[y]:
                if not path[y]:
                    child[x].append(w-t*(f[y]-1))
                bfs[y] = 0
                q.append(y)
    for x in range(n):
        if path[x]:
            if par[x][1] <= 0:
                print("No")
                return
        child[x].sort()
        for i in range(len(child[x])):
            child[x][i] -= t*(i+1)
            if child[x][i] <= 0:
                print("No")
                return
    print("Yes")
    return

if __name__ == "__main__":
    solve()