题目概述

有一棵 $n$ 个节点的树，每个节点有个防御值。有 $m$ 个骑士在树的节点上，如果骑士攻击力大于等于防御值就可以攻占这个节点获得收益并向上攻占，否则凉凉。问每个节点凉了多少骑士，每个骑士在凉之前占了多少节点。

解题报告

听说倍增过不了……不过可并堆也很斯波啊。从下往上合并节点，每次挑出攻击力最小的骑士，如果不能攻占就凉凉，否则打tag。好像DFS会爆栈？拓扑一下就行了。我已经不会左偏树了，随机堆真好用。

示例程序

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=300000,maxm=300000;

int n,m,tp[maxn+5],cnt[maxn+5],dis[maxm+5];LL h[maxn+5],v[maxn+5];
int E,lnk[maxn+5],son[maxn+5],nxt[maxn+5],d[maxn+5],Head,Tail,que[maxn+5];
int RD[1000000],si,ro[maxn+5],ls[maxm+5],rs[maxm+5];LL w[maxm+5],add[maxm+5],mul[maxm+5];int tag[maxm+5];

inline int Rand() {static int pos=0;return RD[pos<1e6?pos++:pos=0];}
inline void Make() {srand(759405);for (int i=0;i<1e6;i++) RD[i]=rand()&1;}
#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
inline void Addmul(int x,LL k) {if (!x) return;w[x]*=k;add[x]*=k;mul[x]*=k;}
inline void Addadd(int x,LL k) {if (!x) return;w[x]+=k;add[x]+=k;}
inline void Addtag(int x,int k) {if (!x) return;dis[x]+=k;tag[x]+=k;}
inline void Pushdown(int p){
    if (mul[p]>1) Addmul(ls[p],mul[p]),Addmul(rs[p],mul[p]),mul[p]=1;
    if (add[p]) Addadd(ls[p],add[p]),Addadd(rs[p],add[p]),add[p]=0;
    if (tag[p]) Addtag(ls[p],tag[p]),Addtag(rs[p],tag[p]),tag[p]=0;
}
int Merge(int A,int B){
    if (!A||!B) return A+B;if (w[A]>w[B]) swap(A,B);int d=Rand();
    Pushdown(A);d?ls[A]=Merge(ls[A],B):rs[A]=Merge(rs[A],B);return A;
}
void Travel(int x) {if (!x) return;Pushdown(x);Travel(ls[x]);Travel(rs[x]);}
inline void Count(int x){
    while (ro[x]&&w[ro[x]]<h[x]) Pushdown(ro[x]),ro[x]=Merge(ls[ro[x]],rs[ro[x]]),cnt[x]++;
    tp[x]?Addmul(ro[x],v[x]):Addadd(ro[x],v[x]);Addtag(ro[x],1);
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    Make();scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%lld",&h[i]);
    for (int i=2,fa;i<=n;i++) scanf("%d%d%lld",&fa,&tp[i],&v[i]),Add(i,fa),d[fa]++;
    for (int i=1;i<=m;i++) {LL x;int y;scanf("%lld%d",&x,&y);w[++si]=x;mul[si]=1;ro[y]=Merge(ro[y],si);}
    for (int i=1;i<=n;i++) if (!d[i]) que[++Tail]=i,Count(i);
    while (Head!=Tail)
        for (int x=que[++Head],j=lnk[x];j;j=nxt[j])
            {int u=son[j];ro[u]=Merge(ro[u],ro[x]);d[u]--;if (!d[u]) Count(u),que[++Tail]=u;}Travel(ro[1]);
    for (int i=1;i<=n;i++) printf("%d\n",cnt[i]);for (int i=1;i<=m;i++) printf("%d\n",dis[i]);return 0;
}