若水而净万物

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: 

.....