2809: [Apio2012]dispatching 可并堆 左偏树

 1 #include 2 #include 3 #include
 4 #include 5 #include 6 #include 7 using namespace std;
 8 const int maxn=100100;
 9 int n,m;
10 int ch[maxn][2]={},siz[maxn]={},sum[maxn]={},cnt[maxn]={},rt[maxn]={};
11 int fa[maxn]={},val[maxn]={},l[maxn]={};
12 int y[maxn],nex[maxn]={},head[maxn]={},tot=0;
13 long long ans=0;
14 void init(int x,int yi){
15     y[++tot]=yi;nex[tot]=head[x];head[x]=tot;
16 }
17 void updata(int x){
18     siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+1;
19     sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+val[x];
20 }
21 int merge(int x,int y){
22     if(x==0)return y;if(y==0)return x;
23     if(val[x]val[y])swap(x,y);
24     ch[x][1]=merge(ch[x][1],y);
25     if(cnt[ch[x][1]]>cnt[ch[x][0]])
26         swap(ch[x][1],ch[x][0]);
27     cnt[x]=cnt[ch[x][1]]+1;
28     updata(x);
29     return x;
30 }
31 void dfs(int x){
32     for(int i=head[x];i;i=nex[i]){
33         dfs(y[i]);
34         rt[x]=merge(rt[x],rt[y[i]]);
35         while(sum[rt[x]]>m){rt[x]=merge(ch[rt[x]][0],ch[rt[x]][1]);}
36     }ans=max(ans,(long long)l[x]*(long long)siz[rt[x]]);
37 }
38 int main(){
39     scanf("%d%d",&n,&m);
40     for(int i=1;i){
41         scanf("%d%d%d",&fa[i],&val[i],&l[i]);
42         sum[i]=val[i];rt[i]=i;siz[i]=1;
43         if(fa[i])init(fa[i],i);
44     }
45     dfs(1);
46     printf("%lld\n",ans);
47     return 0;
48 }