做法和APIO2012派遣 那道题目类似
在树上DFS，维护当前子树的小根堆
因为需要合并孩子们的信息，使用左偏树就可以了
每次弹出死亡骑士，对剩余骑士打上奖励标记
至于标记的下传和更改，只需要每次在需要遍历到这个点之前push_down就可以了
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cstdlib>
#include<algorithm>
using namespace std; typedef long long LL;
const int maxn=300010;
int n,m;
int a[maxn],rt[maxn],fa[maxn],c[maxn];
int ans1[maxn],ans2[maxn];
LL f[maxn],k[maxn],b[maxn],s[maxn];
int h[maxn],cnt=0;
int dep[maxn];
struct edge{
int to,next;
}G[maxn];
struct Tree{
int L,R,dis;
LL v,k,b;
}t[maxn];
void add(int x,int y){++cnt;G[cnt].to=y;G[cnt].next=h[x];h[x]=cnt;}
void Get_mark(int a,LL k,LL b){
if(a==0)return;
t[a].v=t[a].v*k+b;
t[a].k*=k;t[a].b*=k;t[a].b+=b;
}
void push_down(int a){
Get_mark(t[a].L,t[a].k,t[a].b);
Get_mark(t[a].R,t[a].k,t[a].b);
t[a].k=1;t[a].b=0;
}
int merge(int a,int b){
if(!a||!b)return a+b;
push_down(a);push_down(b);
if(t[a].v>t[b].v)swap(a,b);
t[a].R=merge(t[a].R,b);
if(t[t[a].R].dis>t[t[a].L].dis)swap(t[a].L,t[a].R);
t[a].dis=t[t[a].R].dis+1;
return a;
}
void DFS(int u){
for(int i=h[u];i;i=G[i].next){
int v=G[i].to;
dep[v]=dep[u]+1;
DFS(v);
Get_mark(rt[v],k[v],b[v]);
rt[u]=merge(rt[u],rt[v]);
}
while(rt[u]&&t[rt[u]].v<f[u]){
push_down(rt[u]);ans1[u]++;
ans2[rt[u]]=dep[c[rt[u]]]-dep[u];
rt[u]=merge(t[rt[u]].L,t[rt[u]].R);
}return;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)scanf("%lld",&f[i]);
for(int i=2;i<=n;++i){
scanf("%d%lld%lld",&fa[i],&k[i],&b[i]);
if(k[i]==0)k[i]=1;
else k[i]=b[i],b[i]=0;
add(fa[i],i);
}
for(int i=1;i<=m;++i){
scanf("%lld%d",&s[i],&c[i]);
t[i].v=s[i];t[i].k=1;t[i].b=0;
rt[c[i]]=merge(rt[c[i]],i);
}
DFS(1);
while(rt[1]){
push_down(rt[1]);
ans2[rt[1]]=dep[c[rt[1]]]+1;
rt[1]=merge(t[rt[1]].L,t[rt[1]].R);
}
for(int i=1;i<=n;++i)printf("%d\n",ans1[i]);
for(int i=1;i<=m;++i)printf("%d\n",ans2[i]);
return 0; }