题解：
将所有骑士放在$ci$上，然后树上$dfs$。
每个节点维护一个小根堆，一直$pop$直到$top>=hi$。
然后放加法、乘法标记，将剩下的骑士回溯带回父节点。
代码：
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int N = 300050; template<typename T> inline void read(T&x) { T f = 1,c = 0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();} x = f*c; } int n,m,f[N],hed[N],cnt; ll h[N],a[N],v[N],s[N],c[N],tag_p[N],tag_m[N]; int dis[N],ls[N],rs[N]; int rt[N]; struct EG { int to,nxt; }e[N]; void ae(int f,int t) { e[++cnt].to = t; e[cnt].nxt = hed[f]; hed[f] = cnt; } void add(int x,ll d) { if(!x)return ; tag_p[x]+=d; s[x]+=d; } void mul(int x,ll d) { if(!x)return ; tag_m[x]*=d; tag_p[x]*=d; s[x]*=d; } void pushdown(int x) { if(tag_m[x]!=1) { mul(ls[x],tag_m[x]); mul(rs[x],tag_m[x]); tag_m[x] = 1; } if(tag_p[x]) { add(ls[x],tag_p[x]); add(rs[x],tag_p[x]); tag_p[x] = 0; } } int merge(int x,int y) { if(!x||!y)return x+y; if(s[x]>s[y])swap(x,y); pushdown(x); rs[x] = merge(rs[x],y); if(dis[ls[x]]<dis[rs[x]])swap(ls[x],rs[x]); dis[x] = dis[rs[x]]+1; return x; } int pop(int x) { pushdown(x); return merge(ls[x],rs[x]); } int dep[N]; int a1[N],a2[N]; void dfs(int u) { dep[u] = dep[f[u]]+1; for(int j=hed[u];j;j=e[j].nxt) { int to = e[j].to; dfs(to); rt[u]=merge(rt[u],rt[to]); } while(rt[u]&&s[rt[u]]<h[u]) { a1[u]++; a2[rt[u]]=dep[c[rt[u]]]-dep[u]; rt[u]=pop(rt[u]); } if(!a[u])add(rt[u],v[u]); else mul(rt[u],v[u]); } int main() { read(n),read(m); for(int i=1;i<=n;i++)read(h[i]);h[0]=10000000000000008ll; ae(0,1); for(int i=2;i<=n;i++)read(f[i]),read(a[i]),read(v[i]),ae(f[i],i); for(int i=1;i<=m;i++)read(s[i]),read(c[i]),tag_m[i]=dis[i]=1,rt[c[i]]=merge(rt[c[i]],i); dfs(0); for(int i=1;i<=n;i++)printf("%d ",a1[i]); for(int i=1;i<=m;i++)printf("%d ",a2[i]); return 0; }