好像所有人都写的左偏树 但我不会啊233
首先发现乘的时候 系数不会为负，所以能得到一个关键条件：变化后的战斗力随变化前的战斗力大小单调
所以我们考虑倍增
设hp[x][i]是从x开始一路攻克$2^i$个城池所需要最小的初始生命值
设trans[x][i][0/1]是攻克了$2^i$个城池后攻击力的变化量，0表示乘，1表示加，先乘后加
然后就可以倍增了
#include<bits/stdc++.h>
#define pa pair<ll,ll>
#define CLR(a,x) memset(a,x,sizeof(a))
#define MP make_pair
using namespace std;
typedef long long ll;
const int maxn=3e5+; inline char gc(){
return getchar();
static const int maxs=<<;static char buf[maxs],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,maxs,stdin),p1==p2)?EOF:*p1++;
}
inline ll rd(){
ll x=;char c=gc();bool neg=;
while(c<''||c>''){if(c=='-') neg=;c=gc();}
while(c>=''&&c<='') x=(x<<)+(x<<)+c-'',c=gc();
return neg?(~x+):x;
} int N,M,fa[maxn][];
ll hp[maxn][],trans[maxn][][];
int ans1[maxn],ans2[maxn]; int main(){
//freopen("","r",stdin);
int i,j,k;
N=rd(),M=rd();
for(i=;i<=N;i++) hp[i][]=rd();
fa[][]=N+;
for(i=;i<=N;i++){
fa[i][]=rd();
ll x=rd(),y=rd();
trans[i][][]=;
trans[i][][!x]=y;
for(j=;fa[i][j]&&fa[fa[i][j]][j];j++){
fa[i][j+]=fa[fa[i][j]][j];
hp[i][j+]=max(hp[i][j],(ll)ceil(1.0*(hp[fa[i][j]][j]-trans[i][j][])/trans[i][j][]));
trans[i][j+][]=trans[i][j][]*trans[fa[i][j]][j][]+trans[fa[i][j]][j][];
trans[i][j+][]=trans[i][j][]*trans[fa[i][j]][j][];
}
}
for(i=;i<=M;i++){
ll s=rd();int x=rd(),n=;
for(j=;j>=&&x!=-;j--){
if(fa[x][j]&&hp[x][j]<=s){
s=s*trans[x][j][]+trans[x][j][];
x=fa[x][j];
n+=<<j;
}
}
if(x!=-) ans1[x]++;
ans2[i]=n;
}
for(i=;i<=N;i++)
printf("%d\n",ans1[i]);
for(i=;i<=M;i++)
printf("%d\n",ans2[i]); return ;
}
好好分析空间啊kora!
然而空间大小恶意卡倍增
但是我们这个倍增可以换成三进制的2333
就是把定义里的$2^i$都换成$3^i$
于是$log_3300000=10$，空间就变成了原来的一半
需要注意的一点是，最后在跳倍增的时候，同一个长度可以跳两次（因为是三进制嘛），循环的时候稍微注意一下
#include<bits/stdc++.h>
#define pa pair<ll,ll>
#define CLR(a,x) memset(a,x,sizeof(a))
#define MP make_pair
using namespace std;
typedef long long ll;
const int maxn=3e5+; inline char gc(){
return getchar();
static const int maxs=<<;static char buf[maxs],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,maxs,stdin),p1==p2)?EOF:*p1++;
}
inline ll rd(){
ll x=;char c=gc();bool neg=;
while(c<''||c>''){if(c=='-') neg=;c=gc();}
while(c>=''&&c<='') x=(x<<)+(x<<)+c-'',c=gc();
return neg?(~x+):x;
} int N,M,fa[maxn][];
ll hp[maxn][],trans[maxn][][];
int ans1[maxn],ans2[maxn];
int pw3[]; int main(){
//freopen("","r",stdin);
int i,j,k;
pw3[]=;for(i=;i<=;i++) pw3[i]=pw3[i-]*;
N=rd(),M=rd();
for(i=;i<=N;i++) hp[i][]=rd();
fa[][]=N+;
for(i=;i<=N;i++){
fa[i][]=rd();
ll x=rd(),y=rd();
trans[i][][]=;
trans[i][][!x]=y;
for(j=;j<;j++){
int f=fa[i][j],ff=fa[f][j];
if(!f||!ff||!fa[ff][j]) break;
fa[i][j+]=fa[ff][j];
ll hp1=max(hp[f][j],(ll)ceil(1.0*(hp[ff][j]-trans[f][j][])/trans[f][j][]));
hp[i][j+]=max(hp[i][j],(ll)ceil(1.0*(hp1-trans[i][j][])/trans[i][j][]));
trans[i][j+][]=trans[i][j][]*trans[f][j][]+trans[f][j][];
trans[i][j+][]=trans[i][j][]*trans[f][j][];
trans[i][j+][]=trans[i][j+][]*trans[ff][j][]+trans[ff][j][];
trans[i][j+][]=trans[i][j+][]*trans[ff][j][];
}
}
for(i=;i<=M;i++){
ll s=rd();int x=rd(),n=;
for(j=;j>=&&x!=-;j--){
if(fa[x][j]&&hp[x][j]<=s){
s=s*trans[x][j][]+trans[x][j][];
x=fa[x][j];
n+=pw3[j];j++;
}
}
if(x!=-) ans1[x]++;
ans2[i]=n;
}
for(i=;i<=N;i++)
printf("%d\n",ans1[i]);
for(i=;i<=M;i++)
printf("%d\n",ans2[i]); return ;
}