用左偏树模拟攻占的过程，维护最小值，最多入和出m次，每次log复杂度。
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+;
typedef long long ll;
ll w[N],v[N],mul[N],add[N],h[N];
int l[N],r[N],dis[N],flag[N],c[N],rt[N],head[N],f[N],d[N],die[N],a[N],n,m,cnt;
struct edge
{
int to,nex;
}e[N<<];
void adde(int x,int y)
{
e[++cnt].to=y;e[cnt].nex=head[x];head[x]=cnt;
}
void pushdown(int x)
{
if(mul[x]>)
{
mul[l[x]]*=mul[x];mul[r[x]]*=mul[x];
add[l[x]]*=mul[x];add[r[x]]*=mul[x];
}
if(add[x])
{
add[l[x]]+=add[x];add[r[x]]+=add[x];
}
w[l[x]]*=mul[x];w[l[x]]+=add[x];
w[r[x]]*=mul[x];w[r[x]]+=add[x];
mul[x]=;add[x]=;
}
int merge(int x,int y)
{
if(!x||!y)return x+y;
pushdown(x);pushdown(y);
if(w[x]>w[y])swap(x,y);
r[x]=merge(r[x],y);
if(dis[r[x]]>dis[l[x]])swap(l[x],r[x]);
dis[x]=dis[r[x]]+;
return x;
}
void dfs(int x,int fa)
{
for(int i=head[x];i;i=e[i].nex)
{
int y=e[i].to;
if(y==fa)continue;
d[y]=d[x]+;dfs(y,x);rt[x]=merge(rt[x],rt[y]);
}
while(rt[x]&&w[rt[x]]<h[x])
{
pushdown(rt[x]);
die[rt[x]]=d[c[rt[x]]]-d[x];
flag[x]++;rt[x]=merge(l[rt[x]],r[rt[x]]);
}
if(a[x])mul[rt[x]]*=v[x],add[rt[x]]*=v[x],w[rt[x]]*=v[x],pushdown(rt[x]);
else add[rt[x]]+=v[x],w[rt[x]]+=v[x],pushdown(rt[x]);
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;++i)scanf("%lld",&h[i]);
for(int i=;i<=n;++i)
{
scanf("%d%d%lld",&f[i],&a[i],&v[i]);
adde(i,f[i]);adde(f[i],i);
}
for(int i=;i<=m;++i)
{
scanf("%lld%d",&w[i],&c[i]);
rt[c[i]]=merge(rt[c[i]],i);
mul[i]=;
}
d[]=;dfs(,);
while(rt[])pushdown(rt[]),die[rt[]]=d[c[rt[]]],rt[]=merge(l[rt[]],r[rt[]]);
for(int i=;i<=n;++i)printf("%d\n",flag[i]);
for(int i=;i<=m;++i)printf("%d\n",die[i]);
return ;
}