乍一看，平衡树？
其实左偏树更好做啦(qwq)
每个节点都来棵左偏树维护最小值，(dfs)往上时合并一下，要是攻不下了就把根节点删掉，直到能攻下，
对了，攻下后值会变化怎么办？(lazy)标记一下，和线段树同理
**My complete code: **
#include<cstdio>
#include<iostream>
using namespace std;
typedef long long LL;
const LL maxn=400000;
struct node{
LL to,next;
}dis[maxn];
struct code{
LL val,lazy1,lazy2,dis;
LL son[2];
}tree[maxn];
LL n,m,num; LL scc[maxn],dep[maxn],ans[maxn],belong[maxn],tmp[maxn],k[maxn],def[maxn],change[maxn];
LL head[maxn];
inline void add(LL u,LL v){
dis[++num]=(node){v,head[u]}; head[u]=num;
}
inline void update(LL x){
LL lazy1=tree[x].lazy1,
lazy2=tree[x].lazy2,
son0=tree[x].son[0],
son1=tree[x].son[1];
if(son0){
tree[son0].val=tree[son0].val*lazy1+lazy2;
tree[son0].lazy1*=lazy1;
tree[son0].lazy2=tree[son0].lazy2*lazy1+lazy2;
}
if(son1){
tree[son1].val=tree[son1].val*lazy1+lazy2;
tree[son1].lazy1*=lazy1;
tree[son1].lazy2=tree[son1].lazy2*lazy1+lazy2;
}
tree[x].lazy1=1;
tree[x].lazy2=0;
}
LL merge(LL x,LL y){
if(!x || !y)
return x+y;
update(x);
update(y);
if(tree[x].val>tree[y].val)
swap(x,y);
tree[x].son[1]=merge(tree[x].son[1],y);
if(tree[tree[x].son[1]].dis>tree[tree[x].son[0]].dis)
swap(tree[x].son[1],tree[x].son[0]);
tree[x].dis=tree[tree[x].son[1]].dis+1;
return x;
}
void dfs(LL u,LL fa){
dep[u]=dep[fa]+1;
for(LL i=head[u];i;i=dis[i].next){
LL v=dis[i].to;
dfs(v,u);
if(!k[v]){
tree[belong[v]].val+=change[v];
tree[belong[v]].lazy2+=change[v];
}else{
tree[belong[v]].val*=change[v];
tree[belong[v]].lazy1*=change[v];
tree[belong[v]].lazy2*=change[v];
}
belong[u]=merge(belong[u],belong[v]);
}
while(belong[u] && tree[belong[u]].val<def[u]){
ans[belong[u]]=u;
scc[u]++;
update(belong[u]);
belong[u]=merge(tree[belong[u]].son[0],tree[belong[u]].son[1]);
}
}
int main(){
scanf("%lld%lld",&n,&m);
for(LL i=1;i<=n;++i)
scanf("%lld",def+i);
for(LL i=2;i<=n;++i){
LL u;
scanf("%lld%lld%lld",&u,k+i,change+i);
add(u,i);
}
for(LL i=1;i<=m;++i){
scanf("%lld%lld",&tree[i].val,tmp+i);
tree[i].lazy1=1;
tree[i].lazy2=0;
belong[tmp[i]]=merge(belong[tmp[i]],i);
}
dfs(1,0);
for(LL i=1;i<=n;++i)
printf("%lld
",scc[i]);
for(LL i=1;i<=m;++i)
printf("%lld
",dep[tmp[i]]-dep[ans[i]]);
return 0;
}