problem

There are $ N $ islands numbered from $ 1 $ to $ N $.
Each island has $ N-1 $ bridges, allowing any $ 2 $ island to move to each other across several bridges.
Each bridge has durability, and the durability of the $ i $ th bridge given the input is $ w_i $.
There are $ 1 $ treasures on each island, and you can pick them up while you're on the island.

Yebi, who is currently on the island $ S $, wants to carry all the treasures to the museum on the island $ E $.
Since yebi has ✝ magical power ✝, every time he visits the island $ v $, the durability of all bridges coming out of $ v $ is reduced by $ T $.
When the durability of the bridge drops below $ 0 $, the bridge collapses and cannot be crossed after that.
Can yebi deliver all the treasures to the museum?
However, since yebi is powerful, he can carry as many treasures as he wants at the same time.



output

Output "Yes" if you can deliver all the treasures to the museum, otherwise output "No".
Also, output a line break at the end.

Example

Input

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


Output

Yes
#include <bits/stdc++.h>

using namespace std;

#define ll long long

//#define TEST

struct edge {
	int from = 0, to = 0; ll weight = 0;
	int cnt = 0;
	ll evl = 0; // 評価値
	edge() {}
	edge(int f, int t, ll w) {
		from = f;
		to = t;
		weight = w;
	}
};

int n, s, e;
ll t;
vector<vector<edge*>> g; // 隣接リスト
edge es[100000];
vector<int> parent;

void dfs(int s) { // parentを構築する
	for (auto eg : g[s]) {
		if (eg->from == s && parent[eg->to] == -1) {
			parent[eg->to] = s;
			dfs(eg->to);
		}
		else if (eg->to == s && parent[eg->from] == -1) {
			parent[eg->from] = s;
			dfs(eg->from);
		}
	}
}

void visit(int i) {
	for (auto eg : g[i]) {
		eg->weight -= t;
	}
}

int got = 1;
vector<int> visited;
void solve(int s) {
	for (auto eg : g[s]) {
		int to;
		if (eg->from == s)
			to = eg->to;
		else
			to = eg->from;
		if (visited[to])
			continue;
		if (eg->weight <= 0) {
			cout << "No" << endl;
			exit(0);
		}
		visit(to);
		visited[to] = 1;
		++got;
		solve(to);
		if (eg->weight <= 0) {
			cout << "No" << endl;
			exit(0);
		}
		visit(s);
	}
	if (got == n && s == e) {
		cout << "Yes" << endl;
		exit(0);
	}
}

signed main() {
	cin >> n >> t >> s >> e;
	--s; --e;

	g.resize(n);
	parent.resize(n, -1);

	for (int i = 0; i < n - 1; ++i) {
		int a, b; ll w;
		cin >> a >> b >> w;
		--a; --b;
		edge eg(a, b, w);
		es[i] = eg;
		g[a].push_back(es + i);
		g[b].push_back(es + i);
	}

#ifdef TEST
	cout << "------------es------------" << endl;
	for (int i = 0; i < n - 1; ++i) {
		auto eg = es[i];
		cout << (eg.from) << " " << (eg.to) << " " << (eg.weight) << endl;
	}
#endif

	parent[s] = s;
	dfs(s);

#ifdef TEST
	cout << "----------parent----------" << endl;
	for (auto pi : parent)
		cout << pi << " ";
	cout << endl;
#endif

	vector<int> cnt(n, 1); // 頂点iを何回訪れるか
	cnt[s] -= 2;
	for (auto pi : parent)
		cnt[pi]++;
	int now = e; int prt = parent[e];
	while (now != prt) {
		cnt[prt]--;
		now = prt;
		prt = parent[now];
	}

#ifdef TEST
	cout << "------------cnt-----------" << endl;
	for (auto ci : cnt)
		cout << ci << " ";
	cout << endl;
#endif

	for (int i = 0; i < n - 1; ++i) {
		es[i].cnt = cnt[es[i].from] + cnt[es[i].to];
		es[i].evl = es[i].weight - t * es[i].cnt;
	}

	now = e; prt = parent[e];
	while (now != prt) {
		for (auto eg : g[now]) {
			if ((*eg).from == now && (*eg).to == prt) {
				(*eg).evl = INT_MAX;
				break;
			}
			else if ((*eg).from == prt && (*eg).to == now) {
				(*eg).evl = INT_MAX;
				break;
			}
		}
		now = prt;
		prt = parent[now];
	}

#ifdef TEST
	cout << "-----------edge-----------" << endl;
	for (int i = 0; i < n - 1; ++i) {
		auto eg = es[i];
		cout << (eg.from) << " " << (eg.to) << " " << (eg.evl) << endl;
	}
#endif

	for (int i = 0; i < n; ++i) {
		sort(
			g[i].begin(),
			g[i].end(),
			[](const edge* e1, const edge* e2) {return (e1->evl < e2->evl); }
		);
	}

#ifdef TEST
	cout << "----------edge(sorted)-----" << endl;
	for (int i = 0; i < n; ++i) {
		cout << "i=" << i << endl;
		for (auto eg : g[i])
			cout << (eg->from) << " " << (eg->to) << " " << (eg->evl) << endl;
	}
#endif

	visited.resize(n, 0);
	visited[s] = 1;

	solve(s);

	return 0;
	}
