给定一颗n个节点树，边权为1，树上有m个点被标记，问从树上一个点出发，经过所有被标记的点的最短路程（起终点自选）。同时输出可能开始的编号最小的那个点。M<=N<=123456。
先想：如果所有点都被标记那么怎么样？我们发现对于起点s终点t，如果它们在同一条链上，那么必须先从s往外走，再回来，再经过t，再回到t。走过的路径就是树上所有边*2-s到t的路径。如果它们不在同一条链上，那么s在走到t的过程中访问所有点，走过的路径还是树上所有边*2-s到t的路径。
于是如果所有点都被标记，我们应该找到树的直径。如何找树的直径呢？先随便找一个点，然后找从这个点出发能到达的最远点。这个最远点一定是直径的一段，然后再找一次直径即可。（待证）
所以我们只需要把这棵树转成全被标记的就行了。我们随便找一个标记过的点，将其作为树的根，然后只保留标记各个点所在的那条链的上端，因为它们是唯一且一定会经过的边。然后按照算法来就行了。
但这样做还不够，题目还要求输出可能开始的编号最小的那个点。我们发现如果第一次从根开始找，编号最小的点要么是离根最远的点，要么是离根最远的点所找到的最远的点。而离根最远的点能找到的最远的点实际上都是一样的，这就告诉我们直接取最小编号的点，再找一遍，再取最小值就行了。
给出我丑陋的代码：
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std; const int maxn=;
int n, m, root, printed_num, longest_road;
int printed_list[maxn], printed[maxn], visited[maxn], step[maxn];
vector<int> node[maxn], sons[maxn];
queue<int> q; int make_tree(int pos){
int return_value=, t=, nowson;
visited[pos]=;
for (int i=; i<node[pos].size(); ++i){
nowson=node[pos][i];
if (visited[nowson]) {
sons[pos].push_back(nowson);
continue;
}
t=make_tree(nowson);
if (t) sons[pos].push_back(nowson);
return_value|=t;
}
if (printed[pos]) return_value=;
if (return_value) ++printed_num;
return return_value;
} int main(){
scanf("%d%d", &n, &m);
int t1, t2;
for (int i=; i<n; ++i){
scanf("%d%d", &t1, &t2);
node[t1].push_back(t2);
node[t2].push_back(t1);
}
for (int i=; i<m; ++i){
scanf("%d", &printed_list[i]);
printed[printed_list[i]]=;
}
make_tree(printed_list[]);
if (printed_num==) {
printf("%d\n%d\n", printed_list[], );
return ;
}
root=printed_list[];
memset(visited, , sizeof(visited));
q.push(root);
int nownode, nowson, farthest=, farone=;
while (!q.empty()){
nownode=q.front();
q.pop();
visited[nownode]=;
for (int i=; i<sons[nownode].size(); ++i){
nowson=sons[nownode][i];
if (visited[nowson]) continue;
step[nowson]=step[nownode]+;
q.push(nowson);
}
if (step[nownode]>farthest){
farthest=step[nownode];
farone=nownode;
}
if (step[nownode]==farthest&&farone>nownode)
farone=nownode;
}
int a, b;
a=farone;
farthest=, farone=;
while (!q.empty()) q.pop();
memset(visited, , sizeof(visited));
memset(step, , sizeof(step));
q.push(a);
while (!q.empty()){
nownode=q.front();
q.pop();
visited[nownode]=;
for (int i=; i<sons[nownode].size(); ++i){
nowson=sons[nownode][i];
if (visited[nowson]) continue;
q.push(nowson);
step[nowson]=step[nownode]+;
}
if (step[nownode]>farthest){
farthest=step[nownode];
farone=nownode;
}
if (step[nownode]==farthest&&farone>nownode)
farone=nownode;
}
b=farone;
if (a<b) printf("%d\n", a);
else printf("%d\n", b);
printf("%d", *(printed_num-)-farthest);
return ;
}