### practice080's blog

By practice080, 4 months ago, 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 