题意
有一棵树(n)个节点，每个节点有一个防御值，以及两个属性，表示一个骑士占领该节点后攻击值是加还是乘，有(m)个骑士，有初始位置和初始攻击值，如果攻击值大于该节点的防御值，就能占领该节点，然后更新攻击值，走到父节点，如果攻击值小于防御值，骑士就会死在该节点。
问每个骑士能占领多少个节点，以及每个节点分别有多少个骑士死在那里。
分析
- 第一个问题，考虑对每一个节点，如果我们能知道所有能到达该节点的骑士以及他们的攻击力，显然攻击力小于该节点防御值的就是死在这个节点的骑士。
- 这部分骑士分为两部分，第一部分是初始位置就在这个节点的，第二部分是从下面上来的，这部分可以用dfs来求出，然后考虑用可并堆来维护这些骑士的信息。
- 显然将以该节点为初始位置的骑士和dfs后回溯上来的骑士对应的可并堆进行合并，然后将攻击力小于防御值的骑士去掉，维护大根堆，显然这些骑士也不可能再对上面的节点有贡献。
- 第二个问题，由于骑士走的肯定是树上的一个单向路径，所以只需要记录初始位置的深度和死亡位置的深度即可。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e5+50;
struct Edge{
int v,next;
}e[N],ct[N];
int cnt1,cnt2,head1[N],head2[N];
void init(){
cnt1=0;
cnt2=0;
memset(head1,-1,sizeof(head1));
memset(head2,-1,sizeof(head1));
}
void add(int u,int v,bool tr){
if(tr){
e[cnt1]=Edge{v,head1[u]};
head1[u]=cnt1++;
}else{
ct[cnt2]=Edge{v,head2[u]};
head2[u]=cnt2++;
}
}
int n,m,fa,fi[N],sis[N],k[N],ls[N],rs[N],dis[N],dep[N];
ll f[N],ai[N],vi[N],g[N],ad[N],mu[N];
//对a子树计算标记
void fun(int a,ll add,ll mul){
if(a){
g[a]*=mul;
g[a]+=add;
ad[a]*=mul;
ad[a]+=add;
mu[a]*=mul;
}
}
void pushdown(int a){
fun(ls[a],ad[a],mu[a]);
fun(rs[a],ad[a],mu[a]);
ad[a]=0;
mu[a]=1;
}
int merge(int a,int b){
if(!a || !b){
return a+b;
}
pushdown(a);
pushdown(b);
if(g[a]>g[b]){
swap(a,b);
}
rs[a]=merge(rs[a],b);
if(dis[ls[a]]<dis[rs[a]]){
swap(ls[a],rs[a]);
}
dis[a]=dis[rs[a]]+1;
return a;
}
int pop(int a){
pushdown(a);
return merge(ls[a],rs[a]);
}
int dfs(int u,int d){
//因为是小根堆，这里是a=0，如果是大根堆，a=u ？？？
int a=0;
dep[u]=d;
//合并在这个城池开始的所有骑士
for(int i=head2[u];i!=-1;i=ct[i].next){
int v=ct[i].v;
a=merge(a,v);
}
//合并能从下面上来到这个城池的骑士
for(int i=head1[u];i!=-1;i=e[i].next){
int v=e[i].v;
a=merge(a,dfs(v,d+1));
}
//攻击力不够的骑士死在这个城池，记录死的位置，通过深度可知占领的城池数
while(a && g[a]<f[u]){
k[a]=u;
sis[u]++;
a=pop(a);
}
//更新攻击力，回溯到上一层城池进行攻击
if(ai[u]){
fun(a,0,vi[u]);
}else{
fun(a,vi[u],1);
}
return a;
}
int main(){
// freopen("in.txt","r",stdin);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%lld",&f[i]);
}
init();
for(int i=2;i<=n;i++){
scanf("%d%lld%lld",&fa,&ai[i],&vi[i]);
add(fa,i,true);
}
for(int i=1;i<=m;i++){
scanf("%lld%d",&g[i],&fi[i]);
add(fi[i],i,false);
}
dfs(1,1);
for(int i=1;i<=n;i++){
printf("%d
",sis[i]);
}
for(int i=1;i<=m;i++){
printf("%d
",dep[fi[i]]-dep[k[i]]);
}
return 0;
}