好题。

题目传送门

思路：

首先一个贪心的思路是能打怪加血就尽量打怪，嗑药的时间越往后那么你得到的血量就越多。

而对于当前我们能打的怪，肯定是优先打 s_i 最小，同时 g_i 最大的最优，这个可以用小根堆来维护

考虑 \sum [t_i=2] \le 10，我们可以对嗑药的集合进行状压。

定义 f_{S} 为嗑完集合状态为 S 中的药后，所能获得的最大血量，同时记录状态为 S 时，树上节点的可达性。一个状态对应的可达节点一定构成了一个联通块。

先处理出不嗑一瓶药的所能获得的最大血量。枚举所有状态，枚举嗑了集合里的哪瓶药产生了当前集合。

对于当前枚举的药，需要用 bfs 判断在原状态的基础上是否能到达对应节点，即是否合法。然后将可达节点全部压入小根堆继续计算嗑完这瓶药后打怪所能得到的最大血量。

注意每次计算完后，都需判断一次当前血量是否大于 s_i 的最大值，否则会炸 long long。

总复杂度为 O(2^mnm\log n)，m 是药的数量。

code

#include<bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define FileIn(x) freopen(""#x".in","r",stdin)
#define FileOut(x) freopen(""#x".out","w",stdout)
#define debug(x) cerr<<""#x" = "<< (x) <<'\n'
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 Int;
const int N=510,M=10,inf=2e9;
bool StM;
vector<int>G[N];
int n,t[N],s[N],g[N];
int rt=1,m=0,id[N],Re[N];
ll f[(1<<M)],ma;
bitset<N>vis[(1<<M)];
struct enermy{
    int up,del,id;
    bool operator<(const enermy&a) const{
        if(a.up==up) return a.del>del;
        return a.up<up;
    }
};
priority_queue<enermy>q;
void Main()
{
    cin>>n;m=0;
    for(int i=2,x;i<=n;i++)
    {
        cin>>x>>t[i]>>s[i]>>g[i];
        G[x].push_back(i);ma=max(ma,(ll)s[i]);
    }
    for(int i=2;i<=n;i++)
        if(!(t[i]&1)) Re[id[i]=++m]=i;
    for(int to:G[rt])
        if(t[to]&1) q.push({s[to],g[to],to});
    ll cur=1;vis[0][rt]=1;
    while(q.size())
    {
        auto [up,del,now]=q.top();q.pop();
        if(up>cur) break;
        cur+=del;vis[0][now]=1;
        for(int to:G[now])
            if(t[to]&1) q.push({s[to],g[to],to});
    }
    f[0]=cur;
    if(f[0]>ma) return void(cout<<"Yes\n");
    for(int S=1;S<(1<<m);S++)
    {
        f[S]=-inf;
        for(int i=1;i<=m;i++)
        {
            if(S&(1<<i-1)){
                if(f[S^(1<<i-1)]<0) continue;
                bool OK=false;
                queue<int>p;p.push(rt);
                while(p.size())
                {
                    int now=p.front();p.pop();
                    for(int to:G[now])
                    {
                        if(id[to]==i) OK=true;
                        if(vis[S^(1<<i-1)][to]) p.push(to);
                    }
                    if(OK) break;
                }
                if(!OK) continue;
                while(q.size()) q.pop();
                for(int to:G[rt])
                {
                    if(t[to]&1){
                        if(vis[S^(1<<i-1)][to]) q.push({0,0,to});
                        else q.push({s[to],g[to],to});
                    }
                    else if(S&(1<<id[to]-1)) q.push({0,0,to});
                }
                ll cur=1ll*f[S^(1<<i-1)]*g[Re[i]];
                bitset<N>per;per.reset();
                while(q.size())
                {
                    auto [up,del,now]=q.top();q.pop();
                    if(up>cur) break;
                    cur+=del;per[now]=1;
                    for(int to:G[now])
                    {
                        if(t[to]&1){
                            if(vis[S^(1<<i-1)][to]) q.push({0,0,to});
                            else q.push({s[to],g[to],to});
                        }
                        else if(S&(1<<id[to]-1)) q.push({0,0,to});
                    }
                }
                if(cur>f[S])
                    f[S]=cur,vis[S]=per;
                if(f[S]>ma) return void(cout<<"Yes\n");
            }
        }
    }
    cout<<"No\n";
}
bool EdM;
int main()
{
    cerr<<fabs(&StM-&EdM)/1024.0/1024.0<<" MB\n";
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int StT=clock();
    int T=1;
    while(T--) Main();   
    int EdT=clock();
    cerr<<1e3*(EdT-StT)/CLOCKS_PER_SEC<<" ms\n";
    return 0;
}