题解
用一个平衡树维护能攻占到u点的骑士，合并到父亲的时候去掉攻击力小于父亲生命值的那部分，只要把那棵树拆掉并且将树中的所有骑士更新一下答案，用无旋式treap很好写
合并的时候只要启发式合并就可以了
复杂度\(O(n \log^2 n)\)
代码
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define enter putchar('\n')
#define space putchar(' ')
#define MAXN 300005
//#define ivorysi
using namespace std;
typedef long long int64;
typedef double db;
typedef unsigned int u32;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) out(x / 10);
putchar('0' + x % 10);
}
u32 Rand() {
static u32 x = 20020421;
return x += x << 2 | 1;
}
struct Treap_node {
Treap_node *lc,*rc;
int siz,id;int64 val,mul,add;
u32 pri;
void addm(int64 v) {
val *= v;mul *= v;add *= v;
}
void addv(int64 v) {
val += v;add += v;
}
void push_down() {
if(mul != 1) {
if(lc) lc->addm(mul);
if(rc) rc->addm(mul);
mul = 1;
}
if(add) {
if(lc) lc->addv(add);
if(rc) rc->addv(add);
add = 0;
}
}
void update() {
siz = 1;
if(lc) siz += lc->siz;
if(rc) siz += rc->siz;
}
}pool[MAXN * 2],*tail = pool,*rt[MAXN],*que[MAXN];
int tot;
Treap_node *Newnode(int v,int id) {
Treap_node *res = tail++;
res->val = v;res->siz = 1;res->mul = 1;res->add = 0;
res->lc = res->rc = 0;res->pri = Rand();res->id = id;
return res;
}
void Split_val(Treap_node *u,Treap_node *&L,Treap_node *&R,int64 v) {
if(!u) {L = R = NULL;return;}
u->push_down();
if(u->val < v) {
L = u;
Split_val(u->rc,L->rc,R,v);
L->update();
}
else {
R = u;
Split_val(u->lc,L,R->lc,v);
R->update();
}
}
Treap_node *Merge(Treap_node *L,Treap_node *R) {
if(!L) return R;
if(!R) return L;
L->push_down();R->push_down();
if(L->pri > R->pri) {L->rc = Merge(L->rc,R);L->update();return L;}
else {R->lc = Merge(L,R->lc);R->update();return R;}
}
Treap_node* Insert(Treap_node *u,Treap_node *v) {
Treap_node *L,*R;
Split_val(u,L,R,v->val);
return Merge(Merge(L,v),R);
}
struct node {
int to,next;
}E[MAXN * 2];
int head[MAXN],sumE,N,M;
int fa[MAXN],a[MAXN],dep[MAXN],ans1[MAXN],ans2[MAXN],c[MAXN];
int64 v[MAXN],s[MAXN],h[MAXN];
vector<int> kn[MAXN];
void add(int u,int v) {
E[++sumE].to = v;
E[sumE].next = head[u];
head[u] = sumE;
}
void Init() {
read(N);read(M);
for(int i = 1 ; i <= N ; ++i) read(h[i]);
for(int i = 2 ; i <= N ; ++i) {
read(fa[i]);read(a[i]);read(v[i]);
add(fa[i],i);add(i,fa[i]);
}
for(int i = 1 ; i <= M ; ++i) {
read(s[i]);read(c[i]);
kn[c[i]].pb(i);
}
}
void get_tree(Treap_node *u) {
u->push_down();
if(u->lc) get_tree(u->lc);
que[++tot] = u;
if(u->rc) get_tree(u->rc);
}
void dfs(int u) {
Treap_node *L,*R;
dep[u] = dep[fa[u]] + 1;
for(int i = head[u] ; i ; i = E[i].next) {
int v = E[i].to;
if(v != fa[u]) {
dfs(v);
Split_val(rt[v],L,R,h[u]);
if(L) {
ans1[u] += L->siz;
tot = 0;get_tree(L);
for(int j = 1 ; j <= tot ; ++j) ans2[que[j]->id] = dep[c[que[j]->id]] - dep[u];
}
if(R) {
if(R->siz > (rt[u] ? rt[u]->siz : 0)) swap(R,rt[u]);
if(!R) continue;
tot = 0;get_tree(R);
for(int j = 1 ; j <= tot ; ++j) {
que[j]->mul = 1;que[j]->add = 0;que[j]->lc = que[j]->rc = 0;que[j]->siz = 1;
rt[u] = Insert(rt[u],que[j]);
}
}
}
}
int si = kn[u].size();
for(int i = 0 ; i < si ; ++i) {
if(s[kn[u][i]] >= h[u]) {
rt[u] = Insert(rt[u],Newnode(s[kn[u][i]],kn[u][i]));
}
else {ans2[kn[u][i]] = 0;ans1[u]++;}
}
if(rt[u]) {
if(a[u] == 0) rt[u]->addv(v[u]);
else rt[u]->addm(v[u]);
}
if(u == 1 && rt[u]) {
tot = 0;get_tree(rt[u]);
for(int j = 1 ; j <= tot ; ++j) ans2[que[j]->id] = dep[c[que[j]->id]];
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Init();
dfs(1);
for(int i = 1 ; i <= N ; ++i) {out(ans1[i]);enter;}
for(int i = 1 ; i <= M ; ++i) {out(ans2[i]);enter;}
}