[CF592D]Super M

题目大意：
给定一颗n个节点树，边权为1，树上有m个点被标记，问从树上一个点出发，经过所有被标记的点的最短路程，以及可行的最小的端点编号。（起终点自选）
M<=N<=123456

思路：
随便定一个标记节点为根，然后以该节点开始遍历，将不是标记节点的叶节点剪掉，剩下的边数为P。求出树的直径L。答案即为2*P-L。
另外注意一定要保证节点编号最小。

#include<cstdio>
#include<cctype>
#include<vector>
#include<algorithm>
inline int getint() {
    int ch;
    while(!isdigit(ch=getchar()));
    int x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
const int N=123457,inf=0x7fffffff;
int n,m;
bool a[N]={0};
struct Edge {
    int to;
    bool cut;
};
std::vector<Edge> e[N];
inline void add_edge(const int u,const int v) {
    e[u].push_back((Edge){v,false});
    e[v].push_back((Edge){u,false});
}
int u=inf,x=inf,v=inf,l=0;
void find_u(const int x,const int parent,const int depth) {
    if(depth>l) {
        l=depth;
        u=x;
    }
    else if(depth==l) {
        u=std::min(u,x);
    }
    for(unsigned int i=0;i<e[x].size();i++) {
        if(e[x][i].to==parent||e[x][i].cut) continue;
        find_u(e[x][i].to,x,depth+1);
    }
}
void find_v(const int x,const int parent,const int depth) {
    if(depth>l) {
        l=depth;
        v=x;
    }
    else if(depth==l) {
        v=std::min(v,x);
    }
    for(unsigned int i=0;i<e[x].size();i++) {
        if(e[x][i].to==parent||e[x][i].cut) continue;
        find_v(e[x][i].to,x,depth+1);
    }
}
bool cut(const int x,const int parent) {
    bool ret=true;
    for(unsigned int i=0;i<e[x].size();i++) {
        if(e[x][i].to==parent) continue;
        if(cut(e[x][i].to,x)) {
            e[x][i].cut=true;
            n--;
        }
        else {
            ret=false;
        }
    }
    return ret&&!a[x];
}
int main() {
    n=getint()-1,m=getint();
    for(int i=0;i<n;i++) add_edge(getint(),getint());
    int x=inf;
    for(int i=0;i<m;i++) {
        int t=getint();
        a[t]=true;
        x=std::min(x,t);
    }
    cut(x,0);
    find_u(x,0,0);
    find_v(u,0,0);
    printf("%d
%d
",std::min(u,v),(n<<1)-l);
    return 0;
}