├ 测试数据 01：答案正确... 0ms
├ 测试数据 02：答案正确... 0ms
├ 测试数据 03：答案正确... 0ms
├ 测试数据 04：答案正确... 0ms
├ 测试数据 05：答案正确... 0ms
├ 测试数据 06：答案正确... 0ms
├ 测试数据 07：答案正确... 0ms
├ 测试数据 08：答案正确... 0ms
├ 测试数据 09：答案正确... 0ms
├ 测试数据 10：答案正确... 0ms
-------------------------
Accepted 有效得分：100 有效耗时：0ms

虽有LTC的论文，但该题的技术分析还是有必要写一下，否则即使AC，也会被弄得晕头转向。。。

题目大意是给一棵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: 

.....

I happily submitted the output to OnlineJudge...soon........................WA!.... @#$##@@...

How can it be true!Since I had written a CHECK to check my answer,my output WAS a Sudoku:
You can see the input(Squares sharing the same color must contain the same number, squares with different colors may contain the same number):

see my output:

1 2 3 4 5 9 6 7 8
5 6 9 2 7 8 1 4 3
8 4 7 3 6 1 2 9 5
2 7 1 9 3 6 8 5 4
3 8 5 1 2 4 9 6 7
4 9 6 5 8 7 3 2 1
7 3 8 6 9 5 4 1 2
9 1 2 7 4 3 5 8 6
6 5 4 8 1 2 7 3 9
It was WRONG?Oh,my god!

we finally got just 7pt.But I think we can at least get 16pt or more.(if we ACed H,F,L...........)However, it is not an end for us, it HAVE JUST BEGUN....we'll be back!

1。路径压缩 

function Find(now:longint):longint;
begin
     if now=fa[now] then Find:=now
                    else
             begin
                  Find:=Find(fa[now]);
                  fa[now]:=Find;
             end;
end;

2。启发式合并

procedure Union_Set;
begin
     a_fa:=Find(a);
     b_fa:=Find(b);
     if rank[a_fa]<rank[b_fa] then fa[a_fa]:=b_fa
                              else
          begin
               fa[b_fa]:=a_fa;
               if rank[a_fa]=rank[b_fa] then inc(rank[a_fa]);
          end;
end;

最简单的题目见NOI2002_Day1_Galaxy

那么就很容易转移了:(k,m)=min{(k-1,j)+[k,m-j]{0<=j<=m},(k-1,m)+1},边界自己想吧。。。。。对于这个节点i,算完所有的(1,m),(2,m),...,(x,m)后,[i,m+1]就等于(x,m)(这里+1是因为i这个节点要保留),每次算出(i,B)后,动态更新下ans就行了...Dp时候的顺序可以记忆化搜索,也可以按后序遍历的顺序进行Dp...

尽管讲了这么多,感觉还是有很多细节问题没有讲清楚,这还是要自己思考一下的,这里只是提供了一个大致的
思路而已...(更多时候，这个思路可能只有作者本人才能看懂的--!)。如果谁有更好的方法,欢迎留言:)

题目二： 贪吃的九头龙（NOI2002_DAY1）
题目大意是给一棵树，再给m种点，这些点要覆盖这棵树的所有节点，且每种种类的点至少要用一次，还规定第一种点必须恰好用K次。这棵树的每一条边都有一个权值（每条边的权值可能不同）。对于某条边，若这条边的两个顶点种类相同，则总权值需要加上这条边的权值。问总权值最少是多少。（可能描述的有些模糊，不懂的看一下原题吧。。。）

首先，要明确一点，就是除了m=2的情况外，如果有的边的两个顶点种类相同，那么这种种类一定是第一种！这能保证解是最优的！发现了这个，就意味着问题解决了一半了。接下来就是状态表示了。。
不难想到用[i,j]表示节点i，恰有j个节点被第一种类的点覆盖，总权值最小是多少。不！这还不够！我们必
须增加一维！这一维不是0就是1，0表示节点i被第一种类的点覆盖，1表示节点i被非第一种类的点覆盖（就是被第二或第三...或第m种类的点覆盖啦--！）。即状态是[i，j，0/1]怎么转移？这不禁联想到上面的第一题，如果还是这样进行一重Dp,那也就是退化成单纯的搜索了。。我们必须进行双重Dp!!

下面还是讲一下第二重的Dp:
还是和上题一样，对于一个节点i，它是0或1类型的。这里只举0类型的例子（即不妨假设节点i被第一种类的点覆盖）。我们得到它的儿子的序列1,2,....,x.按照1到X的线性顺序进行动态规划.显然,当我们规划到i的儿子k时,有两种选择,一是这个儿子类型是0,二是这个儿子的类型是1。
转移就不细讲了。因为涉及到很多很多的细节问题，并且不把这些细节问题讲清楚的话，转移就讲不清楚。而讲清楚这些细节问题至少需要1000+个字。所以就不详细展开讲了。。。。-_-！-_-！-_-!。。。。

总结一下。这两道题都是TreeDp,都是需要双重Dp.可以说,它们两的本质是相同的.可是,不同在哪呢?为什么第二题《贪吃的九头龙》要再加一维呢?深入思考,可以看出它们两的转移方式不同,即option不同.对于第一题,转移的时候是对边而言选还是不选的.对于第二题,转移的时候是对点而言选0类型还是选1类型.而状态是记录在点上,而不是记录在边上.所以第一题只要二维而第二题要三维.换句话说,如果我们表示状态的时候把状态记录在边上,那么第二题只要二维而第一题要三维了。上述的一段话正是本文想要说明的关键部分，有些问题虽然形式不同，但本质相同，所以只有把握本质，深入思考，才能豁然开朗。。。。。

刚搞到一个code_to_html的软件Highlight Code Converter，效果感觉不错：）。故把上述第一题的代码附上。

P.S.第二题我写了7KB,很烂,所以不发上来了.

CODE:                                                 

..........

设函数为y=f(x)

mid1=low+(up-low)/3

mid2=up-(up-low)/3

若f(mid1)<f(mid2) ,则min ∈ [low,mid2]（即把up更新为mid2）

                         否则min ∈ [mid1,up]（即把low更新为mid1）

题目意思就是你站在一个点上看一座连续的山，求可看到山的总长度。
我们可以把山的每一条线段分开考虑，分别求出每一条线段能看到的长度，累加起来即可。
精度也没什么要求，时间复杂度也不必考虑。可惜比赛时没看此题。。。

C Gold Transportation pku3228

题目意思就不讲了（虽然本人看成了最小费用最大流），算法就是二分+最大流，二分最长路，如果两点之间的路小于或等于二分的值，则这两点连两条相反的有向 边，且容量为无穷大。在建一个源和一个汇，分别与有黄金的村庄和储存黄金的村庄相连，容量为该村庄的拥有量或储量。求最大流判断即可。

D The Best Travel Design pku3229

考虑到n很小，可以用状态压缩的Dp(即炮兵阵地)。

G Accelerator pku3232

此题又是看错。。郁闷。
只要二分结束时间即可。。。还有要注意用int64。



这四题应该都能做出来。可惜老是理解错题目。。还是要多分析样例，以验证自己的理解是否正确。总得来说这次赛得不够理想，下次再加油吧。