https://codeforces.com/contest/1881/problem/F
不难发现一件事情，我们这里最后的答案所在的点是 1 和 3 号点。
我们有没有发现一个性质：就是这两个点都是红点间的路径上的，而且最后的答案就是最长的红点间的距离的长度除以二上取整。
那么，我们怎么找到最长的红点间的距离呢？
很显然，O(n^2)枚举两个点然后求距离是会超时的。
这里有一个比较奇妙的算法，就是先钦定一个红点为根节点，然后不停地删除每一条边上的叶子节点，直到这个叶子节点为红点位置就停止在这一条树枝上的操作。
接着，我们删完点后，求出整棵树的直径，也就是红点间的最长距离。
具体为什么呢？
因为很显然，我们删完点后，所有的叶子结点都是红色节点，而直径本身就是从一个叶子节点到另外一个叶子节点，所以这个时候我们求出来的答案救赎对的。
最后我们只需要把直径的长度除以二后向上取整即可。
这里删除节点的复杂度是 O(n) 的，而求直径的dfs 也是 O(n) 的，所以最后的复杂度显然就是 O(n) 的。
#include<bits/stdc++.h>
//#define x first
//#define y second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N=4e5+10,M=2010;
int n,k,res;
int e[N],ne[N],h[N],idx;
bool mark[N],st[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs1(int u,int father)//删点
{
int cnt=0;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==father) continue;
dfs1(j,u);
if(!st[j]) cnt++;
}
if(!cnt&&!mark[u]) st[u]=true;
}
int dfs2(int u,int father)//求树的直径
{
int d1=0,d2=0;
for(int i=h[u];~i;i=ne[i])
{
int j=e[i];
if(j==father||st[j]) continue;
int d=dfs2(j,u)+1;
if(d>d1) d2=d1,d1=d;
else if(d>d2) d2=d;
}
res=max(res,d1+d2);
return d1;
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--)
{
memset(h,-1,sizeof h);
memset(mark,0,sizeof mark);
memset(st,0,sizeof st);
cin>>n>>k;
int root;
while(k--)
{
int x;
cin>>x;
mark[x]=true;
root=x;
}
for(int i=0;i<n-1;i++)
{
int a,b;
cin>>a>>b;
add(a,b);
add(b,a);
}
dfs1(root,-1);
res=0;
dfs2(root,-1);
cout<<(res+1)/2<<endl;
}
return 0;
}