有过类似的 idea 啊,怎么撞了 ABC 了/fn。
注意到药最多只有十个,肯定是先尽可能的加,然后再用乘,因此从这上面入手。状压药定点的使用情况,设 \(f_S\) 表示只用掉 \(S\) 这些药最后能够到达的最大力量值,那么有解的充要条件就是存在 \(f_S \geq \max s_i\)。转移方程为 \(f_{S \cup \{ j \}} = f_S \times g_j (j \notin S)\),能够进行转移的 \(j\) 需要符合到达 \(j\) 点前的怪物关都被打通,而打关则是一个贪心扩展的过程,因为肯定从当前能够打的关中挑选最小 \(s\) 的怪打,这可以通过小根堆维护候选集合。记药定点的个数为 \(m\),则复杂度为 \(\mathcal O(2^m n \log n)\)。
#include<bits/stdc++.h>
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define int long long
#define eb emplace_back
#define pb pop_back
#define ins insert
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
#define power(x) ((x)*(x))
using namespace std;
namespace FastIO
{
template<typename T=int> inline T read()
{
T s=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
return s*w;
}
template<typename T> inline void read(T &s)
{
s=0; int w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
s=s*w;
}
template<typename T,typename... Args> inline void read(T &x,Args &...args)
{
read(x),read(args...);
}
template<typename T> inline void write(T x,char ch)
{
if(x<0) x=-x,putchar('-');
static char stk[25]; int top=0;
do {stk[top++]=x%10+'0',x/=10;} while(x);
while(top) putchar(stk[--top]);
if(ch!='~') putchar(ch);
return;
}
}
using namespace FastIO;
namespace MTool
{
#define TA template<typename T,typename... Args>
#define TT template<typename T>
static const int Mod=998244353;
TT inline void Swp(T &a,T &b) {T t=a;a=b;b=t;}
TT inline void cmax(T &a,T b) {a=max(a,b);}
TT inline void cmin(T &a,T b) {a=min(a,b);}
TA inline void cmax(T &a,T b,Args... args) {a=max({a,b,args...});}
TA inline void cmin(T &a,T b,Args... args) {a=min({a,b,args...});}
TT inline void Madd(T &a,T b) {a=a+b>=Mod?a+b-Mod:a+b;}
TT inline void Mdel(T &a,T b) {a=a-b<0?a-b+Mod:a-b;}
TT inline void Mmul(T &a,T b) {a=a*b%Mod;}
TT inline void Mmod(T &a) {a=(a%Mod+Mod)%Mod;}
TT inline T Cadd(T a,T b) {return a+b>=Mod?a+b-Mod:a+b;}
TT inline T Cdel(T a,T b) {return a-b<0?a-b+Mod:a-b;}
TT inline T Cmul(T a,T b) {return a*b%Mod;}
TT inline T Cmod(T a) {return (a%Mod+Mod)%Mod;}
TA inline void Madd(T &a,T b,Args... args) {Madd(a,Cadd(b,args...));}
TA inline void Mdel(T &a,T b,Args... args) {Mdel(a,Cadd(b,args...));}
TA inline void Mmul(T &a,T b,Args... args) {Mmul(a,Cmul(b,args...));}
TA inline T Cadd(T a,T b,Args... args) {return Cadd(Cadd(a,b),args...);}
TA inline T Cdel(T a,T b,Args... args) {return Cdel(Cdel(a,b),args...);}
TA inline T Cmul(T a,T b,Args... args) {return Cmul(Cmul(a,b),args...);}
TT inline T qpow(T a,T b) {int res=1; while(b) {if(b&1) Mmul(res,a); Mmul(a,a); b>>=1;} return res;}
TT inline T qmul(T a,T b) {int res=0; while(b) {if(b&1) Madd(res,a); Madd(a,a); b>>=1;} return res;}
TT inline T spow(T a,T b) {int res=1; while(b) {if(b&1) res=qmul(res,a); a=qmul(a,a); b>>=1;} return res;}
TT inline void exgcd(T A,T B,T &X,T &Y) {if(!B) return X=1,Y=0,void(); exgcd(B,A%B,Y,X),Y-=X*(A/B);}
TT inline T Ginv(T x) {T A=0,B=0; exgcd(x,Mod,A,B); return Cmod(A);}
#undef TT
#undef TA
}
using namespace MTool;
inline void file()
{
freopen(".in","r",stdin);
freopen(".out","w",stdout);
return;
}
bool Mbe;
namespace LgxTpre
{
static const int MAX=510;
static const int inf=2147483647;
static const int INF=4557430888798830399;
int n,m,x,all,top,S;
int t[MAX],s[MAX],g[MAX];
int f[1<<10],use[10],med[MAX],rmed[10];
vector<int> G[MAX];
priority_queue<pii,vector<pii>,greater<pii>> q;
inline void lmy_forever()
{
read(n);
for(int i=2;i<=n;++i) read(x,t[i],s[i],g[i]),G[x].eb(i),t[i]==2?(med[i]=m,rmed[m]=i,++m,void()):cmax(top,s[i]);
f[0]=1,t[1]=1;
for(int i=0;i<(1<<m);++i) if(f[i])
{
while(!q.empty()) q.pop();
q.emplace(mp(-1,1)),all=S=0,memset(use,0,sizeof use);
while(!q.empty())
{
auto [val,now]=q.top(); q.pop();
++all;
if(val>f[i]) break;
if(t[now]==1) f[i]+=g[now],S+=g[now]; else if(!(i>>med[now]&1)) {use[med[now]]=1; continue;}
for(auto to:G[now]) q.emplace(mp((t[to]==2?-1:s[to]),to));
}
if(all==n||f[i]>=top) return puts("Yes"),void();
for(int j=0;j<m;++j) if(use[j]) cmax(f[i|(1<<j)],f[i]*g[rmed[j]]-S);
}
puts("No");
}
}
bool Med;
signed main()
{
// file();
fprintf(stderr,"%.3lf MB\n",abs(&Med-&Mbe)/1048576.0);
int Tbe=clock();
LgxTpre::lmy_forever();
int Ted=clock();
cerr<<1e3*(Ted-Tbe)/CLOCKS_PER_SEC<<" ms\n";
return (0-0);
}