The following fact holds.

Whenever you face a defeatable enemy, immediately defeat it.

Here, a defeatable enemy refers to an enemy on a vertex, reachable only via visited vertices, and whose \(s _ i\) is no more than the strength of \(s _ i\).

This is true because if there is a way to defeat all the enemies, where an enemy is not immediately defeated, then one can bring it forward so that the enemy is immediately defeated.

Therefore, if one can defeat all the enemies, then all the enemies can be defeated as follows:

• If there is a defeatable enemy, defeat it.
• Otherwise, take an appropriate medicine.

Consider the following DP (Dynamic Programming).

• \(\operatorname{dp}[S]\coloneqq\) the maximum Takahashi’s strength when he took the medicine in the set \(S\)

By the observation above, it is sufficient to consider the following case: from the state of \(\operatorname{dp}[S\setminus\lbrace i\rbrace]\), take medicine \(i\), and defeat as many enemies as possible.

With an appropriate \(O(N\log N)\) precalculation, a simulation step costs \(O(N)\) time, and the transition occurs \(O(2^PP)\) times, where \(P\) is the number of medicine, for a total complexity of \(O(N(2^PP+\log N))\).

A sample code follows.

#include <iostream>
#include <vector>
#include <ranges>
#include <numeric>
#include <algorithm>
#include <utility>

int main() {
    using namespace std;

    constexpr unsigned long max_strength{1000000000};

    unsigned N;
    cin >> N;

    struct vertex_info {
        unsigned potion_mask;        // set of medicine required to erase this vertex
        unsigned parent;             // parent of this vertex
        unsigned long need_strength; // minimum strength required to erase this vertex
        unsigned long gain;          // strength gained by erasing this vertex (or 0 if there is a medicine on this vertex)
    };
    struct potion_info {
        unsigned index;         // index of vertex
        unsigned long multiply; // ratio of strength when the medicine is taken
    };
    enum vertex_type {
        ENEMY = 1,
        POTION
    };

    vector<vertex_info> vertex(N - 1);
    vector<potion_info> potion;
    vertex.emplace(begin(vertex), 0, 0, 0, 1); // root
    for (unsigned type, i{1}; auto &&[m, p, strength, gain] : vertex | views::drop(1)) {
        cin >> p >> type >> strength >> gain;
        m = vertex[p].potion_mask;         // The parent must be erased before the vertex itself is erased
        if (type == vertex_type::POTION) { // If it is a medicine
            m |= 1U << size(potion);       // This medicine also has to be taken
            potion.emplace_back(i, exchange(gain, 0));
        }
        if (vertex[--p].gain) // If the parent is enemy
            strength = clamp(vertex[p].need_strength + vertex[p].gain, strength, max_strength);
        else // If the parent is medicine
            strength = clamp(vertex[p].need_strength * potion[bit_width(vertex[p].potion_mask) - 1].multiply, strength, max_strength);
        ++i;
    }

    // Sort the vertex in ascending order of the strength required to erase it
    {
        vector<unsigned> sorted_index(N), sorted_index_inv(N);
        iota(begin(sorted_index), end(sorted_index), 0U);
        ranges::stable_sort(sorted_index, {}, [&vertex](auto i) { return vertex[i].need_strength; });
        for (const auto i : views::iota(0U, N))
            sorted_index_inv[sorted_index[i]] = i;
        for (auto &&[_m, p, _s, _g] : vertex)
            p = sorted_index_inv[p];
        for (auto &&[i, _] : potion)
            i = sorted_index_inv[i];
        for (const auto i : views::iota(0U, N)) {
            const auto j{sorted_index_inv[i]};
            swap(sorted_index_inv[sorted_index[i]], sorted_index_inv[sorted_index[j]]);
            swap(sorted_index[i], sorted_index[j]);
            swap(vertex[sorted_index[i]], vertex[sorted_index[j]]);
        }
        ranges::sort(potion, {}, [](auto &&i) { return i.index; });
        for (unsigned x{}; auto &&[m, p, strength, gain] : vertex) {
            m = 0;
            m = vertex[p].potion_mask;
            if (!gain)
                m |= 1U << x++;
        }
    }

    const auto K{size(potion)};
    // dp[S] := Maximum reachable strength when all the medicine in S are taken but the others are not
    vector<unsigned long> dp(1U << K);

    // vertex reachable without taking the medicine
    dp[0] = 0;
    for (const auto &[_m, _p, need_strength, gain] : vertex | views::filter([](auto &&i) { return i.potion_mask == 0; }))
        if (need_strength <= dp[0])
            dp[0] = min(dp[0] + gain, max_strength + 1);
        else
            break;

    for (const auto drunk_potions : views::iota(0U, 1U << K)) {
        const auto prev_strength{dp[drunk_potions]};
        // medicine that can be taken
        const auto reachable_potion{[prev_strength, &vertex, &potion](auto i) {
            return vertex[potion[i].index].need_strength <= prev_strength;
        }};
        // medicine that are not taken yet
        const auto remaining_potion{[drunk_potions](auto i) { return !(1 & (drunk_potions >> i)); }};
        for (const auto next_potion : views::iota(0U, K) | views::filter(reachable_potion) | views::filter(remaining_potion)) {
            auto now_strength{min(prev_strength * potion[next_potion].multiply, max_strength + 1)};
            const auto next_potions{drunk_potions | (1U << next_potion)};
            // vertex reachable without taking medicine
            const auto reachable_vertex{[next_potions](auto &&v) { return !(v.potion_mask & ~next_potions); }};
            // vertex not erased yet
            const auto remaining_vertex{[drunk_potions, prev_strength](auto &&v) {
                return (v.potion_mask & ~drunk_potions) || prev_strength < v.need_strength;
            }};
            for (const auto &[_m, _p, need_strength, gain] : vertex | views::filter(reachable_vertex) | views::filter(remaining_vertex))
                if (need_strength <= now_strength)
                    now_strength = min(now_strength + gain, max_strength + 1);
                else
                    break;
            dp[next_potions] = max(dp[next_potions], now_strength);
        }
    }

    cout << (dp.back() < vertex.back().need_strength ? "No" : "Yes") << endl;

    return 0;
}