Hi all, my friend asked me a question few months ago.

Problem Statement

Given a tree with $$$N$$$ vertices ($$$v_1, ..., v_N$$$), among them, there is a source vertex $$$v_S$$$ and a destination vertex $$$v_E$$$ ($$$S \ne E$$$, $$$1 \le S,E \le N$$$). Each edge has an integer weight (can be negative, zero, or positive).

Alice starts at $$$v_S$$$ with an initial health value of $$$h$$$, and she wants to reach $$$v_E$$$. When she traverses through an edge with weight $$$w$$$, the weight $$$w$$$ is added to her health value. At any point in time, her health value cannot be negative. After an edge is used, the weight of the edge becomes $$$0$$$. Alice can use the same edge multiple times, but only the first time will affect her health value because the weight of the edge becomes $$$0$$$.

Find out whether Alice can reach $$$v_E$$$ with a non-negative health value.

Constraint

$$$2 \le N \le 2 \times 10^5$$$ （for reference only, the expected solution's complexity needs to be better than $$$O(N^2)$$$)

Example

Example 1

To show why using the same edge multiple times is necessary, consider the following cases (using a degenerated tree for simplicity): $$$S = 3, E = 4, h = 1$$$

$$$v_1$$$ ---(2)--- $$$v_2$$$ ---(-1)--- $$$v_3$$$ ---(-2)--- $$$v_4$$$

The only path for Alice is $$$v_3 \to v_2 \to v_1 \to v_2 \to v_3 \to v_4$$$. Her health value will be $$$1 \to 0 \to 2 \to 2\to 2 \to 0$$$.

Example 2