week11:求树的直径；
随机选点，搜索到距离该点最远的一点，然后从该点出发获得最远点，两点间距即为直径；正常思路
然后看了眼大佬的代码。real服。空间换时间。
每当加入一条边：就当是两条边；
to数组存边号对应的终点，hd数组存起点对应的边号，nx数组存该起点对应的另一条边；
核心代码非常诡异：
int cl(int u,int p){
int a=0,b=0,t;
for(int i=hd[u];i;i=nx[i])//u的每一个方向
if(to[i]!=p)//如果没有走回起点
if((t=cl(to[i],u)+1)>b)//迭代取得ｕ经过i边的最远。（即u为折点）
if((b=t)>a)
t=a,a=b,b=t;//之前ｔ>b>a;现在ａ>b>t;
if((b+=a)>ans)ans=b;//该点一边最远ａ一边最远ｂ；
return a;//经过ｕ的最远；
}
这个代码倒是严格按提示来的，ａ保留了ｕ开始最长，ｂ保留了ｕ开始次长；返回ａ＋b;就是逻辑很难顺下来啊。
看了下ｐｏｊ１８４９的报告
1849的题是这样：ｎ个点，n-1条有权边,从Ｓ点出发的两辆车 遍历完所有节点走过的路最短。
由题可知不成环。那么就只有两种情况：
１．起点在直径上，那么直接求树的直径就好
２．起点不在直径上：最长链只被遍历一遍，其余都是两遍
显然１是２的特殊情形。
用ｂｆｓ吧 因为ｄｆｓ经常用。
所以要Ｓ干嘛。。。觉得我随机找一点开始太浪费时间，从起点开始？
用数组模拟搞过了。
不过ｂｆｓ的正规套路是ｑｕｅｕｅ啊。
步步为营 一视同仁 无解方止
queue<Point> q;
q.push(start);
Point next;
while(!q.empty())//队列不为空继续扩展
{
Point tmp=q.front()；
q.pop();
for(int i = 0; i < 8; ++i)
{
next.row = tmp.row + directR[i];
next.col = tmp..col + directC[i];
if(inmap(next) && !visited[next.row][next.col])//inmap判断是否在地图内
{
next.moves = tmp.moves + 1;
if(next.row == end.row && next.col == end.col)//如果是终点
return next.moves;
q.push(next);//入列
visited[next.row][next.col] = true;//标志为走过
}
}
}
