本文主要是介绍Splay(dispatching)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
原题：APIO 2012 派遣
方法：splay 启发式合并
program dispatching;
const maxn=100000+100;
typelink=^node;node=record x:longint; next:link;end;
varl,r,s,w,f,fa:array[1..maxn]of longint;ge:array[1..maxn]of link;
procedure push(var x:link;const t:longint);inline;var p:link;
beginnew(p);p^.x:=t;p^.next:=x;x:=p;
end;
procedure update(const x:longint);inline;
begins[x]:=s[l[x]]+s[r[x]]+1;f[x]:=f[l[x]]+f[r[x]]+w[x];
end;
procedure left(var i:longint);var j:longint;
beginj:=r[i];r[i]:=l[j];l[j]:=i;s[j]:=s[i];f[j]:=f[i];update(j);i:=j;
end;
procedure right(var i:longint);var j:longint;
beginj:=l[i];l[i]:=r[j];r[j]:=i;s[j]:=s[i];f[j]:=f[i];update(j);i:=j;
end;
procedure insert(var i:longint;const j:longint);
beginif i=0 then begin i:=j; exit; end;if w[j]<=w[i] then begininsert(l[i],j);right(i);end else begininsert(r[i],j);left(i);end;
end;
function union(x,y:longint):longint;
var ll,rr:longint;
beginif (x=0)or(y=0) then exit(x+y);if x=y then exit(x);ll:=l[y];l[y]:=0;rr:=r[y];r[y]:=0;s[y]:=0; insert(x,y);l[y]:=union(l[x],ll);r[y]:=union(r[x],rr);update(x);exit(x);
end;
while find(x:longint):longint;
beginwhile x<>0 do beginif s[l[x]]+1=k then exit(X);if s[l[x]]<k then x:=l[x] elsebegin dec(k,s[l[x]]); x:=r[x]; end;end;
end;var n,i,h,t,ans:longint; p:link;
procedure getans(const x:longint);inline;
begin if x>ans then ans:=x;end;
beginreadln(n);for i:=1 to n do begin readln(fa[i],w[i],l[i]); push(ge[fa[i]],i);end;for i:=1 to n do begin s[i]:=1;tt[i]:=i;end;while h<t do begin inc(h); p:=ge[q[h]]; while p<>nil do begin inc(t);q[t]:=p^.x;p:=p^.next;tt[q[h]]:=union(ls[x]);end;end;for i:=n downto 1 do beginp:=ge[q[i]];while p<>nil do begintt[q[i]]:=union(tt[p^.x]);x:=x^.next;endgetans(l[q[i]]*find(tt[q[i]]));end;
end;这篇关于Splay(dispatching)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
