这种图论题已经变得简单了。。。
/* D */
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <deque>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cstring>
#include <climits>
#include <cctype>
#include <cassert>
#include <functional>
#include <iterator>
#include <iomanip>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,1024000") #define sti set<int>
#define stpii set<pair<int, int> >
#define mpii map<int,int>
#define vi vector<int>
#define pii pair<int,int>
#define vpii vector<pair<int,int> >
#define rep(i, a, n) for (int i=a;i<n;++i)
#define per(i, a, n) for (int i=n-1;i>=a;--i)
#define clr clear
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define lson l, mid, rt<<1
#define rson mid+1, r, rt<<1|1 const int maxn = ;
vi vc[maxn], vc2[maxn];
bool visit[maxn];
bool mark[maxn];
int markp[maxn], pre[maxn];
int mx[maxn], mx_[maxn];
int n, m, length = ;
int mn = INT_MAX, ans = INT_MAX; void bfs(int s) {
queue<int> Q;
int u, v, sz; Q.push(s);
visit[s] = true;
pre[s] = ; while (!Q.empty()) {
u = Q.front();
Q.pop();
sz = SZ(vc[u]);
rep(i, , sz) {
v = vc[u][i];
if (!visit[v]) {
visit[v] = true;
pre[v] = u;
Q.push(v);
}
}
}
} void dfs3(int v) {
if (visit[v])
return; visit[v] = true;
int u = pre[v]; length += ;
vc2[u].pb(v);
vc2[v].pb(u);
if (u)
dfs3(u);
} void dfs(int u, int fa) {
int v, sz = SZ(vc2[u]); mx[u] = mx_[u] = ;
rep(i, , sz) {
v = vc2[u][i];
if (v == fa)
continue; dfs(v, u);
if (mx[v]+ > mx[u]) {
mx_[u] = mx[u];
mx[u] = mx[v] + ;
} else if (mx[v]+ > mx_[u]) {
mx_[u] = mx[v]+;
}
} #ifndef ONLINE_JUDGE
printf("u = %d, mx[u] = %d, mx_[u] = %d\n", u, mx[u], mx_[u]);
#endif
} void dfs2(int u, int fa, int pmx) {
int v, sz = SZ(vc2[u]);
int cmx = max(mx[u], pmx), tmp; if (length-cmx < mn) {
mn = length - cmx;
ans = u;
} else if (length-cmx==mn && u<ans) {
ans = u;
} rep(i, , sz) {
v = vc2[u][i];
if (v == fa)
continue; if (mx[v]+ == mx[u]) {
tmp = max(pmx, mx_[u])+;
} else {
tmp = max(pmx, mx[u])+;
} dfs2(v, u, tmp);
}
} int main() {
ios::sync_with_stdio(false);
#ifndef ONLINE_JUDGE
freopen("data.in", "r", stdin);
freopen("data.out", "w", stdout);
#endif int u, v, x; scanf("%d %d", &n, &m);
rep(i, , n) {
scanf("%d %d", &u, &v);
vc[u].pb(v);
vc[v].pb(u);
} rep(i, , m) {
scanf("%d", &x);
markp[i] = x;
mark[x] = true;
} bfs(x);
memset(visit, false, sizeof(visit));
visit[x] = true;
rep(i, , m)
dfs3(markp[i]);
dfs(x, );
dfs2(x, , ); printf("%d\n%d\n", ans, mn); #ifndef ONLINE_JUDGE
printf("time = %d.\n", (int)clock());
#endif return ;
}