BZOJ2809 dispatching 【可并堆】

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3  
 4 const int maxn = 102000;
 5  
 6 int n,m;
 7 int b[maxn],c[maxn],l[maxn],sz[maxn];
 8 long long tot[maxn];
 9 int dis[maxn],val[maxn],ch[maxn][2],pts[maxn];
10 vector <int> g[maxn];
11 long long ans = 0;
12  
13 int merge(int r1,int r2){
14     if(r1 == 0) return r2; if(r2 == 0) return r1;
15     if(val[r1] > val[r2]){
16     ch[r1][1] = merge(ch[r1][1],r2);
17     if(dis[ch[r1][0]] < dis[ch[r1][1]]) swap(ch[r1][0],ch[r1][1]);
18     if(ch[r1][1]) dis[r1] = dis[ch[r1][1]] + 1;
19     else dis[r1] = 0;
20     return r1;
21     }else{
22     ch[r2][1] = merge(r1,ch[r2][1]);
23     if(dis[ch[r2][0]] < dis[ch[r2][1]]) swap(ch[r2][0],ch[r2][1]);
24     if(ch[r2][1]) dis[r2] = dis[ch[r2][1]] + 1;
25     else dis[r2] = 0;
26     return r2;
27     }
28 }
29  
30 void read(){
31     scanf("%d%d",&n,&m);
32     for(int i=1;i<=n;i++) scanf("%d%d%d",&b[i],&c[i],&l[i]);
33     for(int i=1;i<=n;i++){g[b[i]].push_back(i);}
34 }
35  
36 void dfs(int now){
37     for(int i=0;i<g[now].size();i++){
38     dfs(g[now][i]);
39     sz[now] += sz[g[now][i]];
40     tot[now] += tot[g[now][i]];
41     }
42     sz[now]++; tot[now] += c[now];
43     for(int i=0;i<g[now].size();i++)pts[now]=merge(pts[now],pts[g[now][i]]);
44     while(tot[now] > m){
45     tot[now] -= val[pts[now]];sz[now]--;
46     pts[now] = merge(ch[pts[now]][0],ch[pts[now]][1]);
47     }
48     ans = max(ans,1ll*l[now]*sz[now]);
49 }
50  
51 void work(){
52     for(int i=1;i<=n;i++) pts[i] = i,val[i] = c[i];
53     dfs(g[0][0]);
54     printf("%lld",ans);
55 }
56  
57 int main(){
58     read();
59     work();
60     return 0;
61 }