题目描述
奶牛们想建立一个新的城市。它们想建立一条长度为 Len 的主线大街，然后建立 K 条小街,每条小街的尽头有一间房子(小街的其它位置没有房子)。每条小街在主线大街的P_i 处分支, 小街的长度用L_i表示。FJ想知道最远的两个房子之间的距离是多少。
输入
第 1 行: 两个整数 Len 和K，意义如题目描述。
第2…K+1行: 每行两个整数P_i和L_i，对应着一条小街的信息。
输出
输出共一行一个整数，即最远的两个房子之间的距离。
样例输入
【输入样例1】
5 4
5 6
2 2
0 3
2 7
【输入样例2】
5 4
2 4
2 2
2 10
2 7
样例输出
【输出样例1】
16
【输出样例2】
17
数据范围限制
对于30%的数据： 1≤Len≤500；2≤K≤100；1≤L_i≤1,000；
对于60%的数据： 1≤Len≤5,000；2≤K≤5,000；1≤L_i≤1,000,000；
对于100%的数据：1≤Len≤100,000,000；2≤K≤500,000；0≤P_i≤Len；1≤L_i≤100,000,000；
提示
【样例1解释】主线大街长度是5，有4条小街，分别位于距离主线大街 0、2、 2、 5 处。这4条小街的长度分别是3、 2、 7、 6。注意：主线大街的同一个地点可以有多条小街；房子 #1 和房子 #4 的距离最远，最远距离是16。
题解：
树的直径。
铺垫：
- 树的直径指数上相距最长的两个点。
- 寻找方法： 先从某个结点找距离最长的结点v，这是直径的一段，再以这个点找距离最长的结点u，那么这棵树的直径是uv。
思路：
我们把第一个小街设为根节点，就可以出现如右图的的的一棵树。
所以我们找树的直径时就可以用for来搞定。
for(int i=2;i<=k;i++){
int o=p[i]-p[1]+l[i]+l[1];
if(o>ans){
ans=o;
d=i;
}
}
ans=0;
for(int i=1;i<=k;i++){
if(i!=d){
int o=abs(p[i]-p[d])+l[i]+l[d];
if(o>ans){
ans=o;
v=i;
}
}
}
printf("%d",ans);