左偏树加lazy操作即可
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <iostream>
# include <algorithm>
# define ll long long
# define RG register
# define IL inline
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
IL ll Read(){
RG ll x = 0, z = 1; RG char c = getchar();
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';
return x * z;
}
const int MAXN(300010);
struct Left{
int id, dis;
ll lazy_c, lazy_j;
Left *ch[2];
IL Left(RG int pos){
id = pos;
lazy_c = dis = 1;
lazy_j = 0;
}
} *rt[MAXN];
struct Edge{
int to, nt;
} edge[MAXN];
int die[MAXN], up[MAXN], ft[MAXN], a[MAXN], n, m, cnt, deep[MAXN] = {0, 1}, c[MAXN];
ll h[MAXN], s[MAXN], v[MAXN];
IL void Add(RG int u, RG int to){
edge[cnt] = (Edge){to, ft[u]}; ft[u] = cnt++;
}
IL int Dis(RG Left *x){
return x == NULL ? 0 : x -> dis;
}
IL void Updata(RG Left *x){
if(Dis(x -> ch[0]) < Dis(x -> ch[1])) swap(x -> ch[0], x -> ch[1]);
x -> dis = Dis(x -> ch[1]) + 1;
}
IL void Cov(RG Left *x, RG ll add, RG ll mul){
if(x == NULL) return;
x -> lazy_c *= mul; (x -> lazy_j *= mul) += add;
(s[x -> id] *= mul) += add;
}
IL void Pushdown(RG Left *x){
if(x -> lazy_c == 1 && !x -> lazy_j) return;
Cov(x -> ch[0], x -> lazy_j, x -> lazy_c);
Cov(x -> ch[1], x -> lazy_j, x -> lazy_c);
x -> lazy_j = 0; x -> lazy_c = 1;
}
IL Left *Merge(RG Left *x, RG Left *y){
if(x == NULL) return y;
if(y == NULL) return x;
Pushdown(x); Pushdown(y);
if(s[x -> id] > s[y -> id]) swap(x, y);
x -> ch[1] = Merge(x -> ch[1], y);
Updata(x);
return x;
}
IL void Pop(RG Left *&x){
RG Left *tmp = x;
Pushdown(x);
x = Merge(x -> ch[0], x -> ch[1]);
delete tmp;
}
IL void Dfs(RG int u){
for(RG int e = ft[u]; e != -1; e = edge[e].nt){
RG int to = edge[e].to;
deep[to] = deep[u] + 1;
Dfs(to);
rt[u] = Merge(rt[u], rt[to]);
}
while(rt[u] != NULL && s[rt[u] -> id] < h[u]){
up[rt[u] -> id] = deep[c[rt[u] -> id]] - deep[u];
die[u]++; Pop(rt[u]);
}
if(a[u]) Cov(rt[u], 0, v[u]);
else Cov(rt[u], v[u], 1);
}
int main(){
Fill(ft, -1);
n = Read(); m = Read();
for(RG int i = 1; i <= n; i++)
h[i] = Read();
for(RG int i = 2, f; i <= n; i++){
f = Read(); a[i] = Read(); v[i] = Read();
if(f) Add(f, i);
}
for(RG int i = 1; i <= m; i++){
s[i] = Read(); c[i] = Read();
RG Left *tmp = new Left(i);
rt[c[i]] = Merge(rt[c[i]], tmp);
}
Dfs(1);
while(rt[1] != NULL) up[rt[1] -> id] = deep[c[rt[1] -> id]], Pop(rt[1]);
for(RG int i = 1; i <= n; i++)
printf("%d\n", die[i]);
for(RG int i = 1; i <= m; i++)
printf("%d\n", up[i]);
return 0;
}