题目大意：有$n$个点的树，第$i$个节点有一个权值$h_i$，$m$个骑士，第$i$个骑士攻击力为$v_i$，一个骑士可以把从它开始的连续的父亲中比它小的节点攻破，攻破一个节点可以把攻击力加或乘一个数（乘的数大于$0$）（每个骑士独立），问每个骑士可以攻破多少个点，每个点会阻挡住多少个骑士。
题解：可以把所有骑士一起考虑，建一个小根堆，存可以攻打到这个点的骑士，每个若堆顶小于该点，就弹出，写一个打标记的可并堆就行了。
卡点：快读中读入$long\;long$的部分返回值变成$int$
C++ Code：
#include <algorithm>
#include <cstdio>
#include <cctype>
namespace __IO {
namespace R {
int x, ch, f;
inline int read() {
ch = getchar(); f = 1;
while (isspace(ch)) ch = getchar();
if (ch == '-') f = -1, ch = getchar();
for (x = ch & 15, ch = getchar(); isdigit(ch); ch = getchar()) x = x * 10 + (ch & 15);
return x * f;
}
long long X;
inline long long readll() {
ch = getchar(); f = 1;
while (isspace(ch)) ch = getchar();
if (ch == '-') f = -1, ch = getchar();
for (X = ch & 15, ch = getchar(); isdigit(ch); ch = getchar()) X = X * 10 + (ch & 15);
return X * f;
}
}
}
using __IO::R::read;
using __IO::R::readll; #define maxn 300010 int head[maxn], cnt;
struct Edge {
int to, nxt;
} e[maxn << 1];
inline void addedge(int a, int b) {
e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt;
} namespace Heap {
int fa[maxn], lc[maxn], rc[maxn], dis[maxn];
long long M[maxn], A[maxn], V[maxn];
inline void Mul(int rt, long long num) {
if (rt) M[rt] *= num, A[rt] *= num, V[rt] *= num;
}
inline void Add(int rt, long long num) {
if (rt) A[rt] += num, V[rt] += num;
}
inline void pushdown(int rt) {
long long &__M = M[rt], &__A = A[rt];
if (__M != 1) {
Mul(lc[rt], __M);
Mul(rc[rt], __M);
__M = 1;
}
if (__A) {
Add(lc[rt], __A);
Add(rc[rt], __A);
__A = 0;
}
} int __merge(int x, int y) {
if (!x || !y) return x | y;
pushdown(x), pushdown(y);
if (V[x] > V[y]) std::swap(x, y);
rc[x] = __merge(rc[x], y), fa[rc[x]] = x;
if (dis[lc[x]] < dis[rc[x]]) std::swap(lc[x], rc[x]);
dis[x] = dis[rc[x]] + 1;
return x;
}
int merge(int x, int y) {
fa[x] = fa[y] = 0;
return __merge(x, y);
} int insert(int rt, long long val, int pos) {
V[pos] = val, M[pos] = 1, A[pos] = 0;
return merge(rt, pos);
}
int pop(int rt) {
pushdown(rt);
return merge(lc[rt], rc[rt]);
}
} int n, m;
int a[maxn], c[maxn], dead[maxn], num[maxn];
int rt[maxn], dep[maxn];
long long w[maxn], v[maxn];
void dfs(int u) {
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
dep[v] = dep[u] + 1;
dfs(v);
rt[u] = Heap::merge(rt[u], rt[v]);
}
while (rt[u] && Heap::V[rt[u]] < w[u]) {
num[u]++, dead[rt[u]] = u;
rt[u] = Heap::pop(rt[u]);
}
if (rt[u]) {
if (a[u]) Heap::Mul(rt[u], v[u]);
else Heap::Add(rt[u], v[u]);
}
} int main() {
n = read(), m = read();
for (int i = 1; i <= n; i++) w[i] = readll();
for (int i = 2, fa; i <= n; i++) {
fa = read(), a[i] = read(), v[i] = readll();
addedge(fa, i);
}
for (int i = 1; i <= m; i++) {
long long V = readll(); c[i] = read();
rt[c[i]] = Heap::insert(rt[c[i]], V, i);
}
dfs(dep[1] = 1);
for (int i = 1; i <= n; i++) printf("%d\n", num[i]);
for (int i = 1; i <= m; i++) printf("%d\n", dep[c[i]] - dep[dead[i]]);
return 0;
}