http://blog.sina.com.cn/s/blog_61034ad90100jqqw.html
题目简述：在树中找三个点A,B,C。使得min(dis[A][C],dis[B][C])+dis[A][B]最大。
本题的一种流传较广的解法是基于分叉点的，即在每一个分叉点的三棵子树中找三条最长的链作为一种解，取最优解，这种算法用dfs初始化之后，dp就是O(N)的了，是非常优秀的算法，详情请见国家集训队2007年陈瑜希的论文。经过我的独立思考，我提出了一种O(N)的，且更加容易实现的算法。
题目简析：认真分析不难发现，其实对于A，B而言，dis[A][C],dis[B][C]谁小谁大是不重要的，因为如果我一定要先去A，在dis[A][C]>dis[B][C]的情况下完全可以将AB调换，因此关键的应该是AB的路径选择。
结论：最优方案中，AB必定为树中的最长链。
证明：
引理1：最优方案中AB必为叶子节点（或只有一个儿子的根），即不存在任何条与A或B关联且不与AB相交的链。
证明：
不妨设B不是叶子节点，如图1，必有B’可以与B相连。显然AB’>AB
（由于等于的情况等价于二者皆可，因此证明中略去等于，下同）
(1)如果CA>CB
原路径为CB+AB.
(1.1)如果CA>CB’.
新路径为CB’+B’A.因为CB’>CB,B’A>BA，因此AB’优于AB。
(1.2)如果CA<CB.
新路径为CA+AB’，因为CA>CB,AB’>AB,因此AB’优于AB.
(2)如果CA<CB
原路径为CA+AB
(1.1)因为CB’>CB,因此CB’>CA，新路径为CA+AB’，优于AB.
综上，命题得证。
我们将这种两端都不可拓展的链叫做极长链。
注：对于任意满足CB’>CB>CA的情况，都是AB’优于AB，下不说明。
引理2:设两条极长链AB，AB’，两条链的公共部分为AO,AB’>AB，除OA和OB外的由O引出的链中，B’O是最长的（如图2），仍有AB不优于AB’。
在这种情况下，C的位置又3种，我们依次讨论。
(2.1)当C处于C1时。
因为B’O>BO,因此CB’>CB
(2.1.1)如果CB>CA,因为CB’>CB,成立。
(2.1.2)如果CA>CB.
(2.1.2.1)如果CA>CB’,CB’+B’A>CB+BA. 成立
(2.1.2.2)如果CB’>CA,CA+AB’>CB+AB成立
综上AB’优于AB。
(2.2)当C处于C2时。
因为B’O>BO,因此CB’>CB
(2.1.1)如果CB>CA,因为CB’>CB,成立。
(2.1.2)如果CA>CB。
(2.1.2.1)如果CA>CB’,CB’+B’A>CB+BA. 成立
(2.1.2.2)如果CB’>CA,CA+AB’>CB+AB成立
综上AB’优于AB。
(2.3)当C处于C3时，
此时原路径为CB+BA或CA+BA.这取决于OA和OB的长度，不妨设OA>BO,则原路径为OB+CO+AB.因此路径长度由CO决定，因为CO<B’O,如果我们可以将B’和C交换，那么原长度将更长，而这种情况下，如果以B’为B，原来的B为C，总的路径长度仍不变。
因此AB不优于AB’.
综上，命题得证。
引理3：树中最长链不差于其他任何链。
证明：对于两条不相交的链a,b.必定存在一条链c与a,b相交，且满足len(a)>len(c)>len(b)，如图3。
AB>CB>CD。
其中BF>EF+ED，CE+EF<AF.
根据引理2，CD不优于CB，CB不优于AB，因此CD不优于AB。总体而言CD不优于AB。
因此对于任意两条链a,b，如果len(a)>len(b)，则b不优于a。
因此，命题得证。
于是，只要先在树中找一条最长链，链两端就是AB，然后枚举C，求最优解即可。
求最长链可以通过两次搜索完成，同时可以完成A到其他的距离的初始化，然后由B出发遍历每一个点，计算出B到其他点的距离，这样计算总距离就O(1)了。
总的时间复杂度是O(N)。
*Author:rj;
*Problem:NOI 2003 逃学的小孩
*Language:C++;
*state:Solved 2010.6.28 19:09
*Memo:树的最长链
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int MaxN=200005;
typedef long long LL;
int h[MaxN]={0},next[MaxN<<1],data[MaxN<<1],value[MaxN<<1],cnt;
int N,M;
int A,B,C;
LL disA[MaxN],disB[MaxN];
bool vis[MaxN];
int q[MaxN];
void AddEdge(int x,int y,int z)
{
next[++cnt]=h[x];h[x]=cnt;data[cnt]=y;value[cnt]=z;
}
void Init()
{
int x,y,z;
scanf("%d%d",&N,&M);
cnt=1;
while (M--)
{
scanf("%d%d%d",&x,&y,&z);
AddEdge(x,y,z);
AddEdge(y,x,z);
}
}
void BFS(int st,LL dis[],int &last)
{
int l,r,p,x,y;
dis[last=st]=0;
memset(vis,0,N+1);
for (vis[q[l=r=0]=st]=1;l<=r;l++)
for (p=h[x=q[l]];p;p=next[p])
if(!vis[y=data[p]])
{
dis[y]=dis[x]+value[p];
if(dis[y]>dis[last])last=y;
vis[q[++r]=y]=1;
}
}
void LongestLink()
{
BFS(1,disA,A);
BFS(A,disA,B);
}
inline LL Min(LL a,LL b){return a>b?b:a;}
inline void GetMax(LL &a,LL b){if(a<b)a=b;}
void Solve()
{
int i,T;
LL ans=0;
LongestLink();
BFS(B,disB,T);
for (i=1;i<=N;i++)GetMax(ans,Min(disA[i],disB[i]));
printf("%I64d",ans+disA[B]);
}
int main()
{
Init();
Solve();
return 0;
}
以下来自陈瑜希论文《多角度思考 创造性思维》
枚举分叉点
将某个点a当作分叉点时，以其为根构造一棵树，对节点Y，就有两种情况：1Y就是节点a；2Y在a的某个孩子节点的子树上。对于情况1，可以把它转化为情况2，只需给a加一个空的孩子节点，认为它和a之间的距离是0即可。既然a是分叉点，那么X和Z就不能在同一棵子树上，X和Y，Y和Z也不能在同一棵子树上。题目中要求的是使|XY|+|YZ|最大，也就是要求2|Ya|+|Za|+|Xa|最大。至此，思路已完全明确，对于以a为分叉点的情形，只需求出到a的最远的3个点，而且这3个点分别处于a的3棵不同的子树之中。如果采用枚举分叉点的方法的话，每次都需要的计算才行，时间复杂度就又成了。
两次遍历
这里，需要改变一下思路。以点1为根，计算出要求的值后，不去枚举其它的节点，而把这棵树再遍历一遍，进行一次BFS，深度小的先访问，深度大的后访问，就保证了访问到某一个节点的时候，其父亲节点已经被访问过了。假设我们现在访问到了点a，我们现在要求的是距点a的3个最远的点，且这3个点到a的路径上不经过除a外的相同节点。显然，这3个点要么位于以a为根的子树中，要么位于以a为根的子树外。如果在以a为根的子树外，那么是一定要通过a的父亲节点与a相连的。至此，思路逐渐清晰起来。此次遍历时，对于点a，检查其父亲节点，只需求出到其父亲节点的最远的，且不在以a为根的子树中的那点即可，再与第一次遍历求得的值进行比较，就可以求出以该点为分叉点时，|XY|+|YZ|的最大值了。具体方法为，每个点记录最大的两个值，并记录这最大的两个值分别是从哪个相邻节点传递来的。当遍历到其某个孩子节点时，只需检查最大值是否是从该孩子节点传递来的，如果是，就取次大值，如果不是，就可以取最大值。这样一来，该算法的时间复杂度和空间复杂度都为，是个非常优秀的算法。
注意
这里提醒大家注意一点，计算过程中的值和最后的结果可能会超过长整型的范围，所以这里需要使用int64或者double类型。
对于树必须进行两次遍历，才能求得最终的最大值。该例题的分析中提出了分叉点的想法，是比较具有创造性的，需要从多个角度思考。因此，在平时的练习中，当对一道题目束手无策时，可从多个角度思考，创造新思维，使题目得到解决。此题遍历两次的方法具有普遍性，在许多题目中都可以得到应用：记录最大的两个值，并记录是从哪个节点传递来的思想方法。这种遍历两次和记录最大的多个值的思想是值得学习的，也是动态规划在树上进行使用的经典方法。
本题的树型动态规划复杂度是线形的，但是也有一部分问题，在线形的时间内无法出解。这类问题的变化更多，从状态的确立到状态的转移，都对思考角度有着更高的要求。这里先举2个例子来说明。
代码来自http://blog.csdn.net/crazy______/article/details/9421359
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=210000;
struct Node{
int flag;
long long t;
};
long long Max;
Node cnt[maxn][4];
bool vis[maxn];
vector<Node> son[maxn];
bool cmp(Node a,Node b)
{
return a.t>b.t;
}
void DFS1(int x)
{
int i,v;
for(i=0;i<3;i++)
cnt[x][i].t=0;
for(i=0;i<son[x].size();i++)
{
v=son[x][i].flag;
if(!vis[v])
{
vis[v]=1;
DFS1(v);
cnt[x][3].t=cnt[v][0].t+son[x][i].t;
cnt[x][3].flag=v;
sort(cnt[x],cnt[x]+4,cmp);
}
}
if(cnt[x][0].t+2*cnt[x][1].t+cnt[x][2].t>Max)
Max=cnt[x][0].t+2*cnt[x][1].t+cnt[x][2].t;
}
void DFS2(int x,long long ff)
{
int i,v;
for(i=0;i<son[x].size();i++) //保证父节点先处理完。
{
v=son[x][i].flag;
if(vis[v])
{
if(cnt[v][0].flag!=x)
cnt[x][3].t=cnt[v][0].t;
else
cnt[x][3].t=cnt[v][1].t;
cnt[x][3].flag=v;
cnt[x][3].t+=ff;
sort(cnt[x],cnt[x]+4,cmp);
if(cnt[x][0].t+2*cnt[x][1].t+cnt[x][2].t>Max)
Max=cnt[x][0].t+2*cnt[x][1].t+cnt[x][2].t;
}
}
for(i=0;i<son[x].size();i++)
{
v=son[x][i].flag;
if(!vis[v])
{
vis[v]=1;
DFS2(v,son[x][i].t);
}
}
}
int main()
{
int N,M;
int i,u,v;
long long t;
Node tmp;
while(scanf("%d%d",&N,&M)==2)
{
for(i=1;i<=N;i++)
son[i].clear();
for(i=1;i<=M;i++)
{
scanf("%d%d%lld",&u,&v,&t);
tmp.flag=v; tmp.t=t; son[u].push_back(tmp);
tmp.flag=u; son[v].push_back(tmp);
}
Max=0;
memset(vis,0,sizeof(vis));
vis[1]=1;
DFS1(1);
memset(vis,0,sizeof(vis));
vis[1]=1;
DFS2(1,0);
printf("%lld\n",Max);
}
return 0;
}