RT

过不了样例

感觉跟题解没区别

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAXN=1e6+5;
ll n,m;
ll h[MAXN];
struct edge{
	ll u,v,nxt;
}e[MAXN];
ll head[MAXN],edge_num;
void add_edge(ll From,ll To){
	edge_num++;
	e[edge_num].u=From;
	e[edge_num].v=To;
	e[edge_num].nxt=head[From];
	head[From]=edge_num;
	return; 
}
ll fa[MAXN],deep[MAXN],v[MAXN];
bool a[MAXN];
void pre(ll now){
	deep[now]=deep[fa[now]]+1;
	for(int i=head[now];i;i=e[i].nxt){
		if(e[i].v==fa[now])continue;
		pre(e[i].v);
	}
	return;
}
struct node{
	ll s,c,id;
}t[MAXN];
vector<node> vec[MAXN];
struct heap{
	ll val,lson,rson,dist,id,lazy_add,lazy_mul;
	void clear(ll qwq){
		val=lson=rson=0,dist=1,id=qwq,lazy_add=0,lazy_mul=1;
		return;
	}
}H[MAXN];
ll rt[MAXN];
void push_down(ll X){
	if(H[X].lazy_add==0&&H[X].lazy_mul==1)return;
	if(H[X].lson){
		H[H[X].lson].lazy_mul*=H[X].lazy_mul;
		H[H[X].lson].lazy_add*=H[X].lazy_mul;
		H[H[X].lson].lazy_add+=H[X].lazy_add;
		H[H[X].lson].val*=H[X].lazy_mul;
		H[H[X].lson].val+=H[X].lazy_add;
	}
	if(H[X].rson){
		H[H[X].rson].lazy_mul*=H[X].lazy_mul;
		H[H[X].rson].lazy_add*=H[X].lazy_mul;
		H[H[X].rson].lazy_add+=H[X].lazy_add;
		H[H[X].rson].val*=H[X].lazy_mul;
		H[H[X].rson].val+=H[X].lazy_add;
	}
	H[X].lazy_add=0,H[X].lazy_mul=1;
	return;
}
ll merge(ll X,ll Y){
	if(!X||!Y)return X+Y;
	push_down(X),push_down(Y);
	if(H[X].val>H[Y].val)swap(X,Y);
	H[X].rson=merge(H[X].rson,Y);
	if(H[H[X].lson].dist<H[H[X].rson].dist)swap(H[X].lson,H[X].rson);
	H[X].dist=H[H[X].rson].dist+1;
	return X;
}
ll find_rt(ll num){
	return num==rt[num]?num:rt[num]=find_rt(rt[num]);
}
ll ans1[MAXN],ans2[MAXN];
void solve(ll now){
	for(int i=head[now];i;i=e[i].nxt){
		if(e[i].v==fa[now])continue;
		solve(e[i].v);
		rt[now]=rt[e[i].v]=merge(rt[now],rt[e[i].v]);
	}
	while(rt[now]&&H[rt[now]].val<h[now]){
		push_down(rt[now]);
		ans1[now]++;
		ans2[rt[now]]=deep[t[rt[now]].c]-deep[now];
		rt[now]=merge(H[rt[now]].lson,H[rt[now]].rson);
	}
	if(a[now]){
		H[rt[now]].lazy_mul*=v[now];
		H[rt[now]].lazy_add*=v[now];
		H[rt[now]].val*=v[now];
	}
	else{
		H[rt[now]].lazy_add+=v[now];
		H[rt[now]].val+=v[now];
	}
	return;
}
int main(){
	cin>>n>>m;
	deep[0]=-1;
	for(int i=1;i<=n;i++)cin>>h[i];
	for(int i=2;i<=n;i++){
		cin>>fa[i]>>a[i]>>v[i];
		add_edge(fa[i],i);
	}
	for(int i=1;i<=m;i++){
		cin>>t[i].s>>t[i].c;
		H[i].lazy_mul=1;
		rt[t[i].c]=merge(rt[t[i].c],i);
	}
	solve(1);
	while(rt[1])push_down(rt[1]),ans2[rt[1]]=deep[t[rt[1]].c],rt[1]=merge(H[rt[1]].lson,H[rt[1]].rson);
	for(int i=1;i<=n;i++)cout<<ans1[i]<<'\n';
	for(int i=1;i<=m;i++)cout<<ans2[i]<<'\n';
	return 0;
}