悬棺求调，20pts,Ac on #3#4

#include<bits/stdc++.h>
using namespace std;
#define ll __int128 
int n,m,dep[300005],bz[300005],ans1[300005],ans2[300005];
vector<int> mp[300005];
struct node{
	int f,rt;
	ll h,a,v;
}p[300005];
struct node2{
	int ls,rs,fa,dis,id;
	ll val,lz1,lz2;
}q[300005];
void pd(int x){
	q[q[x].ls].lz1*=q[x].lz2,q[q[x].ls].lz2*=q[x].lz2,q[q[x].ls].lz1+=q[x].lz1,q[q[x].ls].val*=q[x].lz2,q[q[x].ls].val+=q[x].lz1;
	q[q[x].rs].lz1*=q[x].lz2,q[q[x].rs].lz2*=q[x].lz2,q[q[x].rs].lz1+=q[x].lz1,q[q[x].rs].val*=q[x].lz2,q[q[x].rs].val+=q[x].lz1;
	q[x].lz1=0,q[x].lz2=1;
}
int merge(int x,int y){
	pd(x),pd(y);
	if(!x||!y||x==y) return x|y;
	if(q[x].val<=q[y].val) q[x].rs=merge(q[x].rs,y);
	else swap(x,y),q[x].rs=merge(q[x].rs,y);
	if(q[q[x].ls].dis<q[q[x].rs].dis) swap(q[x].ls,q[x].rs);
	q[x].dis=q[q[x].rs].dis+1;
	return x;
}
int find(int x){
	if(q[x].fa==x) return x;
	else return q[x].fa=find(q[x].fa);
}
void dfs(int u){
	dep[u]=dep[p[u].f]+1;
	int len=mp[u].size();
	for(int i=0;i<len;i++){
		dfs(mp[u][i]);
		int x=find(p[u].rt),y=find(p[mp[u][i]].rt);
		q[x].fa=q[y].fa=merge(x,y);
		p[u].rt=q[x].fa;
	}
	while(p[u].rt!=0&&bz[find(p[u].rt)]==0&&q[find(p[u].rt)].val<p[u].h){
		int x=find(p[u].rt);
		pd(x),ans1[u]++,ans2[x]=dep[u];
		bz[x]=1,q[x].fa=q[q[x].ls].fa=q[q[x].rs].fa=merge(q[x].ls,q[x].rs);
		p[u].rt=q[x].fa,q[x].ls=q[x].rs=0;
		pd(q[x].fa);
	}
	int x=find(p[u].rt);
	if(p[u].a==0) pd(x),q[x].lz1+=p[u].v,q[x].val+=p[u].v;
	else pd(x),q[x].lz2*=p[u].v,q[x].val*=p[u].v;
	pd(x); 
}
signed main(){
	q[0].dis=-1;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		long long x;
		scanf("%lld",&x);
		p[i].h=x;
	}
	for(int i=2;i<=n;i++){
		long long x,y;
		scanf("%d%lld%lld",&p[i].f,&x,&y);
		p[i].a=x,p[i].v=y;
		mp[p[i].f].push_back(i);
	}
	for(int i=1;i<=m;i++){
		long long s;
		int c;
		scanf("%lld%d",&s,&c);
		q[i].fa=i,q[i].lz2=1,q[i].val=s,q[i].id=c;
		int x=find(p[c].rt),y=i;
		q[x].fa=q[y].fa=merge(p[c].rt,i);
		p[c].rt=find(q[y].fa);
		q[0].fa=0;
	}
	dfs(1);
	for(int i=1;i<=n;i++) printf("%lld\n",ans1[i]);
	for(int i=1;i<=m;i++) printf("%lld\n",dep[q[i].id]-ans2[i]);
}