若水而净万物

版权声明：转载时请以超链接形式标明文章原始出处和作者信息及本声明
http://iuaaui.blogbus.com/logs/5369466.html

NOI_2002_Day2_jerrygen_Sol

题目大意是给一棵n个结点的树（n的上限是200000），树的每条边都有一个权值ti,求三个点x,y,z，使满足|XZ|>=|XY|,且使|XY|+|YZ|尽量的大。

这个问题显然不能穷举，一共三个点，那么最多就有C（3，200000）=1333313333400000种状态，会超时。肯定会有O(nlogn)或者是O(n)的算法。考虑到这是棵树，很难找出O(nlogn)的算法，如果是对这棵树进行DFS遍历，那么时间复杂度就是O（n）了。如果时间复杂度是O（n），那么只有贪心或Dp了。。于是，clever的KFC想出了一种Greedy,能过所有的数据。可能这种贪心是对的，只是无法给出准确的证明。。有谁有反例或者证明，欢迎留言：）

贪心如下：

任意找一条树中的最长路，设此最长路的距离为Maxl,最长路的两个端点为n1,n2，设每个结点i（包括n1,n2）到此两个端点的距离分别为dis1[i]、dis2[i],那么所求的答案即为
MAX{min{dis1[i],dis2[i]}}+Maxl(i为树中的每个结点)。。。。。
求最长路，可以进行一次树型动态规划，求每个结点i到n1的距离，可以进行一次DFS,求每个结点i到n2的距离，可以再进行一次DFS。如此时间复杂度为求最长路的时间复杂度（即Dp的复杂度=O(n)）+两次DFS的复杂度(=O(n))=O(n)!!

真是佩服KFC的Imagination和Creation!
其实当我们想不出什么算法的时候，往往可以从数据范围入手寻找可能的算法，并毫不犹豫的拍，就比如这道题，虽然不能给出证明，但毕竟AC了，AC才是王道。。证明可以放在赛后才去考虑。而且有的时候虽然不知道算法正不正确，但还是要思路理清楚，想清楚应该怎么实现，怎么高效的实现，不能应为自以为算法错误而拍出TLE或者是小错误不断的程序，一个错误的算法往往也有可能拍出100+行的程序，这并没有什么奇怪的。。
比如此题，我的代码便有了160多行。

p.s.RS此题代码150行，KFC只有80多行。不过第5个点C++或者FP的go32v2编译会暴栈，只有PASCAL的Win32编译才能AC。。建议C++的同志们用非递归的DFS吧。。。-_-!(此题正确解法见oyy论文)

code: 

const
    maxn=200000;
var
   n,len,n1,n2,i:longint;
   max:int64;
   v:array[1..maxn] of boolean;
   link:array[0..2*maxn,1..3] of longint;
   num,from1,from2:array[1..maxn] of longint;
   opt,dis1,dis2:array[1..maxn] of int64;
procedure setup;
begin
     assign(input,'jerrygen.in');
     assign(output,'jerrygen.out');
     reset(input);
     rewrite(output);
end;
procedure closeit;
begin
     close(input);
     close(output);
end;
procedure init;
var
   i,m,u,v,t:longint;
begin
     readln(n,m);
     for i:=1 to n-1 do
     begin
          readln(u,v,t);
          inc(len);
          link[len,1]:=u;
          link[len,2]:=v;
          link[len,3]:=t;
          inc(len);
          link[len,1]:=v;
          link[len,2]:=u;
          link[len,3]:=t;
     end;
end;
procedure qsort(l,r: longint);
      var
         i,j,x: longint;
         y:array[1..3] of longint;
      begin
         i:=l;
         j:=r;
         x:=link[(l+r) shr 1,1];
         repeat
           while link[i,1]<x do
            inc(i);
           while x<link[j,1] do
            dec(j);
           if not(i>j) then
             begin
                y:=link[i];
                link[i]:=link[j];
                link[j]:=y;
                inc(i);
                j:=j-1;
             end;
         until i>j;
         if l<j then
           qsort(l,j);
         if i<r then
           qsort(i,r);
      end;

procedure prefix;
var
   i:longint;
begin
     qsort(1,2*n-2);
     for i:=1 to 2*n-2 do
       if link[i-1,1]<>link[i,1] then num[link[i,1]]:=i;
end;
procedure Dp(now:longint);
var
   i:longint;
   max1,max2:int64;
begin
     max1:=0;
     max2:=0;
     i:=num[now];
     v[now]:=true;
     max1:=0;
     max2:=0;
     from1[now]:=now;
     from2[now]:=now;
     repeat
          if not(v[link[i,2]]) then
          begin
               Dp(link[i,2]);
               if max1<opt[link[i,2]]+link[i,3] then
               begin
                    max2:=max1;
                    from2[now]:=from1[now];
                    max1:=opt[link[i,2]]+link[i,3];
                    from1[now]:=from1[link[i,2]];
               end
               else
               if opt[link[i,2]]+link[i,3]>max2 then
               begin
                    max2:=opt[link[i,2]]+link[i,3];
                    from2[now]:=from1[link[i,2]];
               end;
          end;
          inc(i);
     until link[i,1]<>now;
     opt[now]:=max1;
     if max1+max2>max then
     begin
          max:=max1+max2;
          n1:=from1[now];
          n2:=from2[now];
     end;
end;
procedure dfs(now:longint);
var
   i:longint;
begin
     i:=num[now];
     v[now]:=true;
     repeat
         if not(v[link[i,2]]) then
          begin
               dis1[link[i,2]]:=dis1[now]+link[i,3];
               dfs(link[i,2]);
          end;
         inc(i);
     until link[i,1]<>now;
end;
procedure dfs1(now:longint);
var
   i:longint;
begin
     i:=num[now];
     v[now]:=true;
     repeat
         if not(v[link[i,2]]) then
          begin
               dis2[link[i,2]]:=dis2[now]+link[i,3];
               dfs1(link[i,2]);
          end;
         inc(i);
     until link[i,1]<>now;
end;
procedure print;
var
   i:longint;
   ans:int64;
begin
     ans:=0;
     for i:=1 to n do
      if dis1[i]<dis2[i] then
       begin
         if dis1[i]>ans then ans:=dis1[i];
       end
       else
       begin
          if dis2[i]>ans then ans:=dis2[i];
       end;
     writeln(max+ans);
end;
begin
     setup;
     init;
     prefix;
     for i:=1 to n do v[i]:=false;
     Dp(1);
     for i:=1 to n do v[i]:=false;
     dis1[n1]:=0;
     dfs(n1);
     dis2[n2]:=0;
     for i:=1 to n do v[i]:=false;
     dfs1(n2);
     print;
     closeit;
end.