注意到牺牲了就不会再有贡献，考虑维护一个小根堆，然后每次从儿子合并之后一直弹直到堆顶不小于防御值。
发现还要整体标记，左偏树能够比较容易地实现标记，当然也可以不下推维护整体标记，只不过有除法的话可能有精度问题。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
using namespace std;
const int BUFF_SIZE = 1 << 20;
char BUFF[BUFF_SIZE],*BB,*BE;
template<class T>
inline void read(T &x)
{
x = 0;
char ch = 0,w = 0;
for(;ch < '0' || ch > '9';w |= ch == '-',ch = gc());
for(;ch >= '0' && ch <= '9';x = (x << 3) + (x << 1) + (ch ^ '0'),ch = gc());
w && (x = -x,1);
}
const int N = 3e5;
int n,m,a[N + 5],w[N + 5],c[N + 5],ans[N + 5];
int fa[N + 5],dep[N + 5];
int to[N + 5],pre[N + 5],first[N + 5];
inline void add(int u,int v)
{
static int tot = 0;
to[++tot] = v,pre[tot] = first[u],first[u] = tot;
}
long long h[N + 5],v[N + 5],s[N + 5];
struct node
{
int dis,fa,id;
int ls,rs;
long long val,add,mul;
} tree[N + 5];
int rt[N + 5],st[N + 5],top;
inline int new_node(int x,long long v)
{
static int tot = 0;
int p = top ? st[top--] : ++tot;
tree[p].val = v,tree[p].id = x,tree[p].dis = tree[p].ls = tree[p].rs = tree[p].add = tree[p].fa = 0,tree[p].mul = 1;
return p;
}
inline void push(int p)
{
if(tree[p].mul ^ 1)
{
tree[tree[p].ls].mul *= tree[p].mul,tree[tree[p].ls].add *= tree[p].mul,tree[tree[p].ls].val *= tree[p].mul;
tree[tree[p].rs].mul *= tree[p].mul,tree[tree[p].rs].add *= tree[p].mul,tree[tree[p].rs].val *= tree[p].mul;
tree[p].mul = 1;
}
if(tree[p].add)
{
tree[tree[p].ls].add += tree[p].add,tree[tree[p].ls].val += tree[p].add;
tree[tree[p].rs].add += tree[p].add,tree[tree[p].rs].val += tree[p].add;
tree[p].add = 0;
}
}
inline void update_add(int p,long long k)
{
p && (tree[p].add += k,tree[p].val += k);
}
inline void update_mul(int p,long long k)
{
p && (tree[p].mul *= k,tree[p].add *= k,tree[p].val *= k);
}
int merge(int p,int q)
{
if(!p || !q)
return p | q;
if(tree[p].val > tree[q].val)
swap(p,q);
push(p),push(q);
tree[tree[p].rs = merge(tree[p].rs,q)].fa = p;
if(tree[tree[p].ls].dis < tree[tree[p].rs].dis)
swap(tree[p].ls,tree[p].rs);
tree[p].dis = tree[tree[p].rs].dis + 1;
return p;
}
inline void pop(int &p)
{
push(p),st[++top] = p,tree[p = merge(tree[p].ls,tree[p].rs)].fa = 0;
}
void dfs(int p)
{
for(register int i = first[p];i;i = pre[i])
dep[to[i]] = dep[p] + 1,dfs(to[i]),rt[p] = merge(rt[p],rt[to[i]]);
for(;rt[p] && tree[rt[p]].val < h[p];w[tree[rt[p]].id] = p,++ans[p],pop(rt[p]));
a[p] ? update_mul(rt[p],v[p]) : update_add(rt[p],v[p]);
}
int main()
{
read(n),read(m);
for(register int i = 1;i <= n;++i)
read(h[i]);
for(register int i = 2;i <= n;++i)
read(fa[i]),read(a[i]),read(v[i]),add(fa[i],i);
for(register int i = 1;i <= m;++i)
read(s[i]),read(c[i]),rt[c[i]] = merge(rt[c[i]],new_node(i,s[i]));
dep[1] = 1,dfs(1);
for(register int i = 1;i <= n;++i)
printf("%d\n",ans[i]);
for(register int i = 1;i <= m;++i)
printf("%d\n",dep[c[i]] - dep[w[i]]);
}