【HDOJ2196】Computer（树的直径，树形DP）

题意：给定一棵N个点树，询问这个树里面每个点到树上其他点的最大距离。

n<=10000

思路：设f[u,1],f[u,2]为以U为根向下的最长与次长，g[u,1],g[u,2]为从哪个儿子转移来

第一次dfs用V更新U，第二次dfs用U更新V，因为有V向U往上走的情况，这样做就可以处理了

可以发现这些数值中取最大值就是树的直径了

 var f,g:array[..,..]of longint;

     head,vet,next,len:array[..]of longint;

     n,x,y,i,tot:longint;

 procedure add(a,b,c:longint);

 begin

  inc(tot);

  next[tot]:=head[a];

  vet[tot]:=b;

  len[tot]:=c;

  head[a]:=tot;

 end;

 procedure dfs(u,fa:longint);

 var e,v,t:longint;

 begin

  e:=head[u];

  while e<> do

  begin

   v:=vet[e];

   if v<>fa then

   begin

    dfs(v,u);

    t:=f[v,]+len[e];

    if t>f[u,] then

    begin

     f[u,]:=f[u,]; g[u,]:=g[u,];

     f[u,]:=t; g[u,]:=v;

    end

     else if t>f[u,] then

     begin

      f[u,]:=t; g[u,]:=v;

     end;

   end;

   e:=next[e];

  end;

 end;

 procedure dfs2(u,fa:longint);

 var e,v,t:longint;

 begin

  e:=head[u];

  while e<> do

  begin

   v:=vet[e];

   if v<>fa then

   begin

    t:=f[u,]+len[e];

    if v=g[u,] then t:=f[u,]+len[e];

    if t>f[v,] then

    begin

     f[v,]:=f[v,]; g[v,]:=g[v,];

     f[v,]:=t; g[v,]:=u;

    end

     else if t>f[v,] then

     begin

      f[v,]:=t; g[v,]:=u;

     end;

    dfs2(v,u);

   end;

   e:=next[e];

  end;

 end;

 begin

  assign(input,'2196.in'); reset(input);

  assign(output,'2196.out'); rewrite(output);

  while not eof do

  begin

   fillchar(head,sizeof(head),);

   tot:=;

   fillchar(f,sizeof(f),);

   fillchar(g,sizeof(g),);

   read(n);

   if n= then break;

   for i:= to n do

   begin

    read(x,y);

    add(i,x,y);

    add(x,i,y);

   end;

   dfs(,-);

   dfs2(,-);

   for i:= to n do writeln(f[i,]);

  end;

  close(input);

  close(output);

 end.

巴特西

【HDOJ2196】Computer（树的直径，树形DP）

最新文章

热门文章