洛谷P3642 [APIO2016]烟火表演

 1 //minamoto
 2 #include<bits/stdc++.h>
 3 #define ll long long
 4 using namespace std;
 5 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
 6 char buf[1<<21],*p1=buf,*p2=buf;
 7 inline int read(){
 8     #define num ch-‘0‘
 9     char ch;bool flag=0;int res;
10     while(!isdigit(ch=getc()))
11     (ch==‘-‘)&&(flag=true);
12     for(res=num;isdigit(ch=getc());res=res*10+num);
13     (flag)&&(res=-res);
14     #undef num
15     return res;
16 }
17 const int N=6e5+5;
18 int n,m,tot,fa[N],w[N],d[N],rt[N],L[N],R[N],dis[N];ll v[N],sum;
19 int merge(int x,int y){
20     if(!x||!y) return x+y;
21     if(v[x]<v[y]) swap(x,y);
22     R[x]=merge(R[x],y);
23     if(dis[L[x]]<dis[R[x]]) swap(L[x],R[x]);
24     dis[x]=dis[R[x]]+1;return x;
25 }
26 int pop(int x){return merge(L[x],R[x]);}
27 int main(){
28 //    freopen("testdata.in","r",stdin);
29     n=read(),m=read();
30     for(int i=2;i<=n+m;++i)
31     fa[i]=read(),w[i]=read(),sum+=w[i],++d[fa[i]];
32     for(int i=n+m;i>=2;--i){
33         ll l=0,r=0;
34         if(i<=n){
35             while(--d[i]) rt[i]=pop(rt[i]);
36             r=v[rt[i]],rt[i]=pop(rt[i]);
37             l=v[rt[i]],rt[i]=pop(rt[i]);
38         }
39         v[++tot]=l+w[i],v[++tot]=r+w[i];
40         rt[i]=merge(rt[i],merge(tot,tot-1));
41         rt[fa[i]]=merge(rt[fa[i]],rt[i]);
42     }
43     while(d[1]--) rt[1]=pop(rt[1]);
44     while(rt[1]) sum-=v[rt[1]],rt[1]=pop(rt[1]);
45     printf("%lld\n",sum);
46     return 0;
47 }