[BZOJ1791] [IOI2008] Island 베이스 링 외향수 + DP

문제에서 각 점은 한 변으로 연결되어 있기 때문에 그림은 여러 개의 기환+외향수이어야 한다.모든 연결 블록에 대해 가장 긴 경로는 한 그루의 나무에 있을 수도 있고 두 그루의 나무의 각 부분에 중간 고리의 경로를 더할 수도 있다.그래서 먼저 그 고리를 찾아내고 모든 나무에 대해 나무형 DP를 하고 뿌리의 가장 긴 거리가 g[i]라고 기록한다.그리고 고리를 전개(1-2-3의 고리를 1-2-3-1-2)하고 거리 접두사와 디스[i]를 유지한다. 이것은 결정 구간이 단조롭게 이동하는 DP이다. 방정식은 f[i]=max{g[j]-dis[j]}+dis[i](i-j+1<=고리 길이)이고 단조로운 대열은 g[j]-dis[j]를 유지하면 된다.최종 답안이 반드시 f[i]의 최대치가 아니라 한 그루의 나무에 있을 수도 있기 때문에 나무형 DP를 집계할 때도 답안을 작성해야 한다.그리고 이 문제는 입력 양식이 좋아서 i행에 입력하고 i->nt[i]의 가장자리를 i->nt[i]를 정향으로 보고, nt[i]->i를 반향으로 본다.이 문제는 필기창고에 써야 할 것 같아. 그렇지 않으면 OJ에서 RE를 할 줄 알아서 쓰기 귀찮아...(그런데 내가 로컬에서 RE 두 점을 측정하고 OLE가 무슨 귀신 코드인지 건네주자.

type
  edge=^edgenode;
  edgenode=record
    t,w:longint;
    next:edge;
  end;
  node=record
    t:longint;
    w:int64;
  end;

const maxn=1000100;
var
  n,i,j,x,y,num,top,oncir:longint;
  ans,all:int64;
  con:array[0..maxn]of edge;
  visit,cir:array[0..maxn]of boolean;
  huan:array[0..maxn]of longint;
  nt:array[0..maxn]of node;
  g,dis:array[0..2*maxn]of int64;
  dl:array[0..2*maxn]of node;
procedure ins(x,y,w:longint);
var
  p:edge;
begin
  new(p);
  p^.t:=y;
  p^.w:=w;
  p^.next:=con[x];
  con[x]:=p;
end;
function max(x,y:int64):int64;
begin
  if x>y then exit(x)
  else exit(y);
end;

procedure findcir(v:longint);
var
  p:edge;
begin
  visit[v]:=true;
  if visit[nt[v].t]=false then findcir(nt[v].t)
  else oncir:=nt[v].t;
  if oncir>0 then begin inc(top); huan[top]:=v; cir[v]:=true; end;
  if oncir=v then oncir:=0;
  visit[v]:=false;
end;
function dfs(v:longint):int64;
var
  p:edge;
  now,o:int64;
begin
  p:=con[v];
  dfs:=0;
  now:=0;
  visit[v]:=true;
  while p<>nil do
  begin
    if cir[p^.t]=false then
    begin
      o:=dfs(p^.t)+p^.w;
      dfs:=max(dfs,o);
      ans:=max(ans,o+now);
      now:=max(now,o);
    end;
    p:=p^.next;
  end;
end;
procedure dp;
var
  i,j,head,tail:longint;
begin
  head:=1;
  tail:=0;
  for i:=1 to 2*top-1 do
  begin
    while (head<=tail)and(dl[head].t<=i-top) do inc(head);
    if i>=top then ans:=max(ans,dl[head].w+g[i]+dis[i]);
    while (head<=tail)and(g[i]-dis[i]>=dl[tail].w) do dec(tail);
    inc(tail);
    dl[tail].t:=i;
    dl[tail].w:=g[i]-dis[i];
  end;
end;
begin
  readln(n);
  for i:=1 to n do
  begin
    readln(x,y);
    nt[i].t:=x;
    nt[i].w:=y;
    ins(x,i,y);
  end;
  fillchar(visit,sizeof(visit),false);
  fillchar(cir,sizeof(cir),false);
  for i:=1 to n do
    if visit[i]=false then
    begin
      oncir:=0;
      top:=0;
      ans:=0;
      findcir(i);
      for j:=1 to top do
        g[j]:=dfs(huan[j]);
      for j:=1 to top-1 do
      begin
        g[j+top]:=g[j];
        huan[j+top]:=huan[j];
      end;
      dis[1]:=0;
      for j:=2 to 2*top-1 do
        dis[j]:=dis[j-1]+nt[huan[j]].w;
      dp;
      all:=all+ans;
    end;
  write(all);
end.