https://blog.csdn.net/wang3312362136/article/details/80615874基本解释
洛谷 攻占城池
用左偏树的思想从底部不断到上面来
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<string.h>
using namespace std;
typedef long long ll;
const ll maxn=3e5+10;
ll flag[maxn],base[maxn]; //城池的val更新方式
ll ch[maxn][2]; //子节点
ll val[maxn],guishu[maxn]; //将领的战力值和第一个城池
ll root[maxn]; //每一个城池的根节点；
ll dep[maxn],dis[maxn]; //dep是用来计算将领的攻占城池数量的， dis是左偏树的深度；
ll ans1[maxn],ans2[maxn]; //城池答案，将领答案；
ll mul[maxn],add[maxn]; //懒惰标记
ll limit[maxn]; //城池耐久值
struct node //邻接表
{
ll v,next;
}G[maxn]; ll head[maxn];ll num=-1;
void build(ll u,ll v)
{
G[++num].v=v;G[num].next=head[u];head[u]=num;
}
void cov(ll x,ll c,ll j)
{
if(!x) return;
val[x]*=c;val[x]+=j; //这里有一个乘和一个加，自然是先乘后加； 这是根据下文这两句来确定的
mul[x]*=c; //这里的确定方式是将已经有的懒惰节点的值与本次加进来的懒惰节点更新；
//已经有的，自然那些要+的，也要乘上这次的数，然后再加上这次要加的数
//注：下次看这里看不懂的话，多看一下肯定会懂的
add[x]*=c;add[x]+=j;
}
void pushdown(ll x)
{ //左右儿子都得更新
cov(ch[x][0],mul[x],add[x]);
cov(ch[x][1],mul[x],add[x]);
mul[x]=1;add[x]=0;
}
ll Merge(ll x,ll y)
{
if(!x||!y) return x+y;
pushdown(x);pushdown(y);//顺便说下每个pushdown为什么要放在这里，首先这里合并一个新的树过来肯定要里面先把该父亲点的信息往下传，鬼知道你合并个新东西进来取代了原来的儿子，他儿子跑别的地方去了就继承不了了
if(val[x]>val[y]) swap(x,y);
ch[x][1]=Merge(ch[x][1],y);
if(dis[ch[x][0]]<dis[ch[x][1]]) swap(ch[x][0],ch[x][1]);
dis[x]=dis[ch[x][1]]+1;
return x;
}
void dfs(ll u,ll fa)
{
dep[u]=dep[fa]+1;
for(ll i=head[u];i!=-1;i=G[i].next){
ll v=G[i].v;
dfs(v,u);
root[u]=Merge(root[u],root[v]);
}
while(root[u]&&val[root[u]]<limit[u]){
pushdown(root[u]);//这里也是要的因为该老人家战败了，接下来轮到他儿子上场比较了，就得先把信息传下去，老人家才好安息
ans1[u]++;//这个就是战败的直接+1；
ans2[root[u]]=dep[guishu[root[u]]]-dep[u];//在这里战败了可以记录多少个城市了
ll t=root[u];
root[u]=Merge(ch[t][0],ch[t][1]);
}
if(flag[u]) cov(root[u],base[u],0);//while一遍后就是第一个可以过该城的士兵，根据左偏树的性质他后面的士兵也可以过去，由于一个一个更新肯定会爆炸，我们运用懒惰标记法
else cov(root[u],1,base[u]);
}
int main()
{
ll n,m;
memset(head,-1,sizeof(head));
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++) scanf("%lld",&limit[i]);
for(ll i=2;i<=n;i++){
ll u;
scanf("%lld%lld%lld",&u,&flag[i],&base[i]);
build(u,i);
}
for(ll i=1;i<=m;i++){
scanf("%lld%lld",&val[i],&guishu[i]);
ll t=guishu[i];
mul[i]=1;
if(!root[t]) root[t]=i;
else root[t]=Merge(root[t],i);
}
dfs(1,0);
while(root[1]){
pushdown(root[1]);
ans2[root[1]]=dep[guishu[root[1]]];
root[1]=Merge(ch[root[1]][0],ch[root[1]][1]);
}
for(ll i=1;i<=n;i++) printf("%lld\n",ans1[i]);
for(ll i=1;i<=n;i++) printf("%lld\n",ans2[i]);
return 0;
}