
为什么 15≤10 啊/kel/ll
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=3e5+10;
struct node{int l,r,d;ll w,mu,pl;}t[N];
ll h[N],val[N];
int n,m,f[N],dep[N],die[N],atk[N];
bool op[N];
vector<int>e[N];
void hmul(int x,ll vl){
t[x].mu*=vl;
t[x].pl*=vl;
t[x].w*=vl;
}
void hplu(int x,ll vl){
t[x].pl+=vl;
t[x].w+=vl;
}
void pushd(int x){
hmul(t[x].l,t[x].mu);
hplu(t[x].l,t[x].pl);
hmul(t[x].r,t[x].mu);
hplu(t[x].r,t[x].pl);
t[x].mu=1;t[x].pl=0;
}
int merge(int x,int y){
if(!x||!y)return x|y;
if(t[x].w>t[y].w)swap(x,y);
assert(t[x].w<=t[y].w);
// printf("%d %d %d %d!\n",x,y,t[x].w,t[y].w);
pushd(x);
t[x].r=merge(t[x].r,y);
if(t[t[x].l].d<t[t[x].r].d)swap(t[x].l,t[x].r);
t[x].d=t[t[x].r].d+1;
return x;
}
int pop(int x){
pushd(x);
return merge(t[x].l,t[x].r);
}
void dfs(int u){
for(int v:e[u]){
dep[v]=dep[u]+1;
dfs(v);
f[u]=merge(f[u],f[v]);
}
while(f[u])
if(t[f[u]].w<h[u])die[u]++,atk[f[u]]=dep[atk[f[u]]]-dep[u],f[u]=pop(f[u]);
else break;
if(!f[u])return;
if(op[u])hmul(f[u],val[u]);else hplu(f[u],val[u]);
}
signed main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&h[i]);
for(int i=2,F;i<=n;i++)scanf("%d%d%d",&F,&op[i],&val[i]),e[F].push_back(i);
for(int i=1;i<=m;i++){
int y;ll x;
scanf("%lld%d",&x,&y);atk[i]=y;
t[i].w=x;t[i].mu=1;t[i].d=1;
f[y]=merge(f[y],i);
}
dfs(1);
while(f[1])atk[f[1]]=dep[atk[f[1]]]+1,f[1]=pop(f[1]);
for(int i=1;i<=n;i++)printf("%d\n",die[i]);
for(int i=1;i<=m;i++)printf("%d\n",atk[i]);
// system("pause");
return 0;
}