次の事実が成り立ちます。

倒せる敵がいた場合、即座に倒してよい。

ただし、ここでの倒せる敵とは「訪れたことのある頂点のみを使って到達でき、\(s _ i\) が現在の高橋くんの強さ以下である頂点にいる敵」を指します。

これは、その敵を後で倒した上ですべての敵を倒すような行動が存在するなら、その敵を倒す順番だけ前倒しにした行動が成立するためです。

よって、すべての敵を倒すことができるなら、次の形式ですべての敵を倒すことができます。

• 倒せる敵がいるなら、その敵を倒す。
• 倒せる敵がいないなら、適切な薬を飲む。

次のような DP を考えます。

• \(\operatorname{dp}[S]\coloneqq\) これまでに飲んだ薬の集合が \(S\) であるときの高橋くんの強さとしてありえる最大値

上の考察から、各 \(i\in S\) ごとに \(\operatorname{dp}[S\setminus\lbrace i\rbrace]\) の状態から薬 \(i\) を飲んで敵を倒せるだけ倒すことをシミュレーションすればよいです。

適切な \(O(N\log N)\) 時間の前処理のもとで、\(1\) 回のシミュレーションには \(O(N)\) 時間かかり、遷移は薬の本数を \(P\) として \(O(2^PP)\) 回なので、全体で \(O(N(2^PP+\log N))\) 時間となります。

実装例は以下のようになります。

#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;        // この頂点を消すまでに飲む必要がある薬の集合
        unsigned parent;             // この頂点の親
        unsigned long need_strength; // この頂点を消すために必要な最小の強さ
        unsigned long gain;          // この頂点を消すことで増える強さ (頂点にあるのが薬のとき、0)
    };
    struct potion_info {
        unsigned index;         // 頂点番号
        unsigned long multiply; // この薬を飲むことで増える強さの倍率
    };
    enum vertex_type {
        ENEMY = 1,
        POTION
    };

    vector<vertex_info> vertex(N - 1);
    vector<potion_info> potion;
    vertex.emplace(begin(vertex), 0, 0, 0, 1); // 根
    for (unsigned type, i{1}; auto &&[m, p, strength, gain] : vertex | views::drop(1)) {
        cin >> p >> type >> strength >> gain;
        m = vertex[p].potion_mask;         // 頂点を消すまでに親が消えている必要がある
        if (type == vertex_type::POTION) { // 薬だった場合
            m |= 1U << size(potion);       // この薬も飲む必要がある
            potion.emplace_back(i, exchange(gain, 0));
        }
        if (vertex[--p].gain) // 親が敵のとき
            strength = clamp(vertex[p].need_strength + vertex[p].gain, strength, max_strength);
        else // 親が薬のとき
            strength = clamp(vertex[p].need_strength * potion[bit_width(vertex[p].potion_mask) - 1].multiply, strength, max_strength);
        ++i;
    }

    // 頂点を「その頂点を消すのに必要な強さ」順に並べ替える
    {
        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] := S に含まれる薬をすべて飲み、それ以外の薬を飲まなかったときに到達できる強さの最大値
    vector<unsigned long> dp(1U << K);

    // 薬を飲まずに到達できる頂点
    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]};
        // 飲める薬
        const auto reachable_potion{[prev_strength, &vertex, &potion](auto i) {
            return vertex[potion[i].index].need_strength <= prev_strength;
        }};
        // まだ飲んでいない薬
        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)};
            // 薬を飲まずに到達できる頂点
            const auto reachable_vertex{[next_potions](auto &&v) { return !(v.potion_mask & ~next_potions); }};
            // まだ消していない頂点
            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;
}