APIO2012派遣

 1 uses math;
 2 const maxn=100000;
 3 type node=record
 4      go,next:longint;
 5      end;
 6 var l,r,d,h,p,s,c,head,ll,fa,num:array[0..maxn+10] of int64;
 7     q:array[0..4*maxn] of longint;
 8     i,n,m,tot,tmp,root:longint;
 9     ans:int64;
10     e:array[0..maxn+10] of node;
11 procedure swap(var x,y:int64);
12  var t:int64;
13  begin
14  t:=x;x:=y;y:=t;
15  end;
16 procedure insert(x,y:longint);
17  begin
18  inc(tot);
19  e[tot].go:=y;e[tot].next:=head[x];head[x]:=tot;
20  end;
21 procedure init;
22  begin
23  readln(n,m);
24  for i:=1 to n do
25   begin
26   readln(fa[i],c[i],ll[i]);
27   if fa[i]0 then insert(fa[i],i) else root:=i;
28   end;
29  end;
30 function merge(x,y:int64):int64;
31  begin
32  if x*y=0 then exit(x+y);
33  if d[x]then swap(x,y);
34  r[x]:=merge(r[x],y);
35  if h[l[x]]then swap(l[x],r[x]);
36  num[x]:=num[l[x]]+num[r[x]]+1;
37  s[x]:=s[l[x]]+s[r[x]]+c[x];
38  h[x]:=h[r[x]]+1;
39  exit(x);
40  end;
41 function del(x:longint):longint;
42  begin
43  exit(merge(l[x],r[x]));
44  end;
45 function work(x:longint):longint;
46  var i,y,t:longint;
47  begin
48  t:=x;
49  d[x]:=c[x];s[x]:=c[x];num[x]:=1;
50  i:=head[x];
51  while i0 do
52   begin
53   y:=e[i].go;
54   t:=merge(t,work(y));
55   i:=e[i].next;
56   end;
57  while s[t]>m do t:=del(t);
58  ans:=max(ans,num[t]*ll[x]);
59  exit(t);
60  end;
61 procedure main;
62  begin
63  ans:=0;
64  tmp:=work(root);
65  writeln(ans);
66  end;
67 begin
68  assign(input,‘dispatching.in‘);assign(output,‘dispatching.out‘);
69  reset(input);rewrite(output);
70  init;
71  main;
72  close(input);close(output);
73 end.