全部RE了,急需求助。
#include<bits/stdc++.h>
using namespace std;
struct Ltree{
int val=0;
int number;
int start;
int lson=0;
int rson=0;
int dist=0;
int add=0;
int mul=1;
}ztree[1000005];
int h[300005],a[300005],v[300005],root[300005]={},dep[300005]={},died[300005]={},killed[300005],head[500005]={},edge[500005],nxt[500005]={},tot=0,ltot=0;
void add_(int a,int b){
nxt[++tot]=head[a];
head[a]=tot;
edge[tot]=b;
}
bool pushdown(int x){
if(ztree[x].mul!=1){
ztree[ztree[x].lson].mul*=ztree[x].mul;ztree[ztree[x].lson].add*=ztree[x].mul;ztree[ztree[x].lson].val*=ztree[x].mul;
ztree[ztree[x].rson].mul*=ztree[x].mul;ztree[ztree[x].rson].add*=ztree[x].mul;ztree[ztree[x].rson].val*=ztree[x].mul;
ztree[x].mul=1;
}
if(ztree[x].add){
ztree[ztree[x].lson].add+=ztree[x].add;ztree[ztree[x].lson].val+=ztree[x].add;
ztree[ztree[x].rson].add+=ztree[x].add;ztree[ztree[x].rson].val+=ztree[x].add;
ztree[x].add=0;
}return 1;
}
int formage(int x,int y){
if(!x||!y) return x+y;
if(ztree[x].val>ztree[y].val) swap(x,y);
pushdown(x);pushdown(y);
ztree[x].rson=formage(ztree[x].rson,y);
if(ztree[ztree[x].lson].dist<ztree[ztree[x].rson].dist) swap(ztree[x].lson,ztree[x].rson);
ztree[x].dist=ztree[ztree[x].rson].dist+1;
return x;
}
void dfs(int now){
for(int i=head[now];i;i=nxt[i]){
int to=edge[i];
dep[to]=dep[now]+1;
dfs(to);
root[now]=formage(root[now],root[to]);
}
while(root[now]&&pushdown(now)&&ztree[root[now]].val<h[now]){
pushdown(root[now]);
died[now]++;killed[ztree[root[now]].number]=dep[ztree[root[now]].start]-dep[now];
root[now]=formage(ztree[root[now]].lson,ztree[root[now]].rson);
}
if(now==1){
while(root[now]){
killed[ztree[root[now]].number]=dep[ztree[root[now]].start]-dep[now]+1;
root[now]=formage(ztree[root[now]].lson,ztree[root[now]].rson);
}
}else if(a[now]){
ztree[root[now]].mul*=v[now];ztree[root[now]].add*=v[now];ztree[root[now]].val*=v[now];
}
else{
ztree[root[now]].add+=v[now];ztree[root[now]].val+=v[now];
}return;
}
int main(void){
ios::sync_with_stdio(false);
int n,m,val;
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>h[i];
for(int i=2;i<=n;i++){
cin>>val>>a[i]>>v[i];
add_(val,i);
}
for(int i=1;i<=m;i++){
++ltot;
cin>>ztree[ltot].val>>val;
ztree[ltot].number=i;ztree[ltot].start=val;
root[val]=formage(root[val],ltot);
}dep[1]=0;dfs(1);
for(int i=1;i<=n;i++) cout<<died[i]<<endl;
for(int i=1;i<=m;i++) cout<<killed[i]<<endl;
return 0;
}