「JLOI2015」城池攻占 可并堆

传送门

分析

如果直接暴力枚举的话肯定会超时

我们可以从下往上遍历，维护一个小根堆

每次到达一个节点把战败的骑士扔出去

剩下的再继续向上合并，注意要维护一下其实的战斗力

可以像线段树那样用一个lazy标记

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn=300005;

typedef long long ll;

ll head[maxn],tot=1;

struct asd{

    ll from,to,next,ty;

    ll val;

}b[maxn];

void ad(ll aa,ll bb,ll cc,ll dd){

    b[tot].from=aa;

    b[tot].to=bb;

    b[tot].ty=cc;

    b[tot].val=dd;

    b[tot].next=head[aa];

    head[aa]=tot++;

}

ll bjc[maxn],bjj[maxn],gjl[maxn];

ll lch[maxn],rch[maxn];

void push_down(ll xx){

    if(xx==0) return;

    if(bjc[xx]!=1){

        gjl[lch[xx]]*=bjc[xx],bjj[lch[xx]]*=bjc[xx],bjc[lch[xx]]*=bjc[xx];

        gjl[rch[xx]]*=bjc[xx],bjj[rch[xx]]*=bjc[xx],bjc[rch[xx]]*=bjc[xx];

        bjc[xx]=1;

    }

    if(bjj[xx]!=0){

        gjl[lch[xx]]+=bjj[xx],bjj[lch[xx]]+=bjj[xx];

        gjl[rch[xx]]+=bjj[xx],bjj[rch[xx]]+=bjj[xx];

        bjj[xx]=0;

    }

}

ll d[maxn],dep[maxn],rt[maxn];

ll h[maxn];

ll bing(ll xx,ll yy){

    if(!xx) return yy;

    if(!yy) return xx;

    push_down(xx),push_down(yy);

    if(gjl[xx]>gjl[yy]) swap(xx,yy);

    rch[xx]=bing(rch[xx],yy);

    if(d[lch[xx]]<d[rch[xx]]) swap(lch[xx],rch[xx]);

    d[xx]=d[rch[xx]]+1;

    return xx;

}

ll killl[maxn],atk[maxn];

ll cnt=0;

void dfs(ll xx){

    for(ll i=head[xx];i!=-1;i=b[i].next){

        ll u=b[i].to;

        dep[u]=dep[xx]+1,dfs(u);

        if(b[i].ty) gjl[rt[u]]*=b[i].val,bjj[rt[u]]*=b[i].val,bjc[rt[u]]*=b[i].val;

        else gjl[rt[u]]+=b[i].val,bjj[rt[u]]+=b[i].val;

        rt[xx]=bing(rt[xx],rt[u]);

    }

    while(rt[xx] && gjl[rt[xx]]<h[xx]){

        killl[xx]++,atk[rt[xx]]=xx,push_down(rt[xx]),rt[xx]=bing(lch[rt[xx]],rch[rt[xx]]);

    }

}

ll jl[maxn];

int main(){

    memset(head,-1,sizeof(head));

    ll n,m;

    scanf("%lld%lld",&n,&m);

    for(ll i=1;i<=n;i++) scanf("%lld",&h[i]);

    for(ll i=2;i<=n;i++){

        ll aa;

        ll bb,cc;

        scanf("%lld%lld%lld",&aa,&bb,&cc);

        ad(aa,i,bb,cc);

    }

    for(ll i=1;i<=m;i++){

        bjc[i]=1;

        ll bb;

        scanf("%lld%lld",&gjl[i],&bb);

        jl[i]=bb;

        rt[bb]=bing(rt[bb],i);

    }

    d[0]=-1;

    dep[1]=1;

    dfs(1);

    for(ll i=1;i<=n;i++) printf("%lld\n",killl[i]);

    for(ll i=1;i<=n;i++) printf("%lld\n",dep[jl[i]]-dep[atk[i]]);

    return 0;

}