[APIO2016]烟火表演

#include
#include#define N 600002
using namespace std;
typedef long long ll;
int deep[N],d[N],n,m,fa[N],T[N],tot;
ll sum,w[N];
inline ll rd(){
    ll x=0;char c=getchar();bool f=0;
    while(!isdigit(c)){if(c==‘-‘)f=1;c=getchar();}
    while(isdigit(c)){x=(x1)+(x3)+(c^48);c=getchar();}
    return f?-x:x;
}
struct tr{
    ll v;int l,r;
}tr[N];
int merge(int x,int y){
    if(!x||!y)return x^y;
    if(tr[x].vtr[y].v)swap(x,y);
    tr[x].r=merge(tr[x].r,y);
    if(deep[tr[x].l]deep[tr[x].r])swap(tr[x].l,tr[x].r);
    deep[x]=deep[tr[x].r]+1;
    return x;
}
inline int pop(int x){return merge(tr[x].l,tr[x].r);}
int main(){
    n=rd();m=rd();
    for(int i=2;ii){
        fa[i]=rd();w[i]=rd();sum+=w[i];d[fa[i]]++;
    }
    for(int i=n+m;i>=2;--i){
        ll l=0,r=0;
        if(in){
            while(--d[i])T[i]=pop(T[i]);
            l=tr[T[i]].v;T[i]=pop(T[i]);
            r=tr[T[i]].v;T[i]=pop(T[i]);
        }
        tr[++tot].v=l+w[i];tr[++tot].v=r+w[i];
        T[i]=merge(T[i],merge(tot-1,tot));
        T[fa[i]]=merge(T[fa[i]],T[i]);
    }
    while(d[1]--)T[1]=pop(T[1]);
    while(T[1]){sum-=tr[T[1]].v;T[1]=pop(T[1]);}
    coutsum;
    return 0;
}