可以先窮舉那個是管理者，然后就發現
其實就是求每個子樹選盡可能多的人，使薪水和小于m
這顯然是從小往大選，可以用啟發式合并
但是用主席樹寫的更簡單一點吧，dfs序之后
每課線段樹不僅維護出現出現個數，然后在維護一個區間和（未離散化之前的）
然后類似查找第k大就可以解決了

1 type node=record 2 po,next:longint; 3 end; 4 link=record 5 l,r,s:longint; 6 sum:int64; 7 end; 8 9 var tree:array[0..100010*20] of link; 10 v,a,b,c,e,sa,rank,h,p:array[0..100010] of longint; 11 w:array[0..100010] of node; 12 n,m,t,tot,len,x,root,i,s:longint; 13 ans:int64; 14 15 function max(a,b:int64):int64; 16 begin 17 if a>b then exit(a) else exit(b); 18 end; 19 20 procedure swap(var a,b:longint); 21 var c:longint; 22 begin 23 c:=a; 24 a:=b; 25 b:=c; 26 end; 27 28 procedure sort(l,r: longint); 29 var i,j,x:longint; 30 begin 31 i:=l; 32 j:=r; 33 x:=a[(l+r) div 2]; 34 repeat 35 while (a[i]<x) do inc(i); 36 while (x<a[j]) do dec(j); 37 if not(i>j) then 38 begin 39 swap(a[i],a[j]); 40 swap(c[i],c[j]); 41 inc(i); 42 j:=j-1; 43 end; 44 until i>j; 45 if l<j then sort(l,j); 46 if i<r then sort(i,r); 47 end; 48 49 procedure add(x,y:longint); 50 begin 51 inc(len); 52 w[len].po:=y; 53 w[len].next:=p[x]; 54 p[x]:=len; 55 end; 56 57 procedure dfs(x:longint); 58 var i,y:longint; 59 begin 60 i:=p[x]; 61 inc(len); 62 a[len]:=x; 63 c[x]:=len; 64 while i<>0 do 65 begin 66 dfs(w[i].po); 67 i:=w[i].next; 68 end; 69 e[x]:=len; 70 end; 71 72 function build(l,r:longint):longint; 73 var m,q:longint; 74 begin 75 inc(t); 76 if l=r then exit(t) 77 else begin 78 q:=t; 79 m:=(l+r) shr 1; 80 tree[q].l:=build(l,m); 81 tree[q].r:=build(m+1,r); 82 exit(q); 83 end; 84 end; 85 86 function add(l,r,last,x,y:longint):longint; 87 var m,q:longint; 88 begin 89 inc(t); 90 if l=r then 91 begin 92 tree[t].s:=tree[last].s+1; 93 tree[t].sum:=tree[last].sum+y; 94 exit(t); 95 end 96 else begin 97 q:=t; 98 m:=(l+r) shr 1; 99 if x<=m then 100 begin 101 tree[q].r:=tree[last].r; 102 tree[q].l:=add(l,m,tree[last].l,x,y); 103 end 104 else begin 105 tree[q].l:=tree[last].l; 106 tree[q].r:=add(m+1,r,tree[last].r,x,y); 107 end; 108 tree[q].sum:=tree[tree[q].l].sum+tree[tree[q].r].sum; 109 tree[q].s:=tree[tree[q].l].s+tree[tree[q].r].s; 110 exit(q); 111 end; 112 end; 113 114 function ask(l,r,a,b,k:longint):longint; 115 var m,s:longint; 116 p:int64; 117 118 begin 119 if l=r then 120 begin 121 p:=tree[b].sum-tree[a].sum; 122 if k>=p then exit(tree[b].s-tree[a].s) //這里要注意下 123 else exit(k div sa[l]); 124 end 125 else begin 126 m:=(l+r) shr 1; 127 p:=tree[tree[b].l].sum-tree[tree[a].l].sum; 128 if p>k then 129 exit(ask(l,m,tree[a].l,tree[b].l,k)) 130 else begin 131 s:=tree[tree[b].l].s-tree[tree[a].l].s; 132 exit(s+ask(m+1,r,tree[a].r,tree[b].r,k-p)); 133 end; 134 end; 135 end; 136 137 begin 138 readln(n,m); 139 for i:=1 to n do 140 begin 141 readln(x,b[i],v[i]); 142 if x=0 then root:=i; 143 add(x,i); 144 end; 145 for i:=1 to n do 146 begin 147 a[i]:=b[i]; 148 c[i]:=i; 149 end; 150 sort(1,n); 151 tot:=1; 152 rank[c[1]]:=1; 153 sa[1]:=a[1]; 154 for i:=2 to n do 155 begin 156 if a[i]<>a[i-1] then 157 begin 158 inc(tot); 159 sa[tot]:=a[i]; 160 end; 161 rank[c[i]]:=tot; 162 end; 163 len:=0; 164 dfs(root); 165 h[0]:=build(1,tot); 166 for i:=1 to n do 167 h[i]:=add(1,tot,h[i-1],rank[a[i]],b[a[i]]); 168 for i:=1 to n do 169 begin 170 s:=ask(1,tot,h[c[i]-1],h[e[i]],m); 171 ans:=max(ans,int64(v[i])*int64(s)); 172 end; 173 writeln(ans); 174 end. View Code

?

轉載于:https://www.cnblogs.com/phile/p/4473026.html

總結

以上是生活随笔為你收集整理的bzoj2809的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。