ICPC Russia Equidistant

In 2019 ICPC subregions structure was changed a little. Now for each subregion, we need to choose the best place for the subregion finals. To make things fair we want to choose a city in such a way that all teams will spend the same amount of time to get there.

To make things simpler we say that all teams will use trains to get to the finals. The railroad system can be represented as a tree where each city is a vertex and some pairs of cities are connected by a railroad. It takes exactly one hour to get from one city to another if they are directly connected.

You are given a description of the railroad system and the cities where teams are located. You need to choose any city that has an equal distance to all teams’ cities or detect that no such city exists.

Input
The first line of the input contains two integers n and m — the number of cities and the number of teams (1≤m≤n≤2⋅105). Each of the following n−1 lines contains two integers vi and ui — the indices of the cities connected by the i-th railroad (1≤vi,ui≤n). It is guaranteed that for each pair of cities there is exactly one simple path connecting them.

The next line contains m integers c1,c2,…,cm — the cities of the teams (1≤ci≤n). All teams are located in different cities.

Output
If it is impossible to choose a city fairly, output a single word “NO”. Otherwise, output a the word “YES” at the first line. The second line should contain a single integer — the city where subregion finals should be held. If there is more than one solution, output any of them.

Examples
inputCopy
6 3
1 2
2 3
3 4
4 5
4 6
1 5 6
outputCopy
YES
3
inputCopy
2 2
1 2
1 2
outputCopy
NO

我们分析可以得知，我们找的点，必然在最远的需要找的点之间。

最远的，不就是树的直径吗？然后我们类似用树的直径去做就可以了，

然后每个点记录前面的那个点，然后找到点x，再对x跑一次bfs，然后判断是不是所有点到x距离相等即可。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=2e5+10;
int n,m,c[N],pre[N],d[N],vis[N],id,mx,id1;
int head[N],nex[N<<1],to[N<<1],tot;
set<int> st;
inline void add(int a,int b){to[++tot]=b; nex[tot]=head[a]; head[a]=tot;}
void bfs(int s){
	queue<int> q;	q.push(s);	vis[s]=1;
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(!vis[to[i]]){
				vis[to[i]]=vis[u]+1;	pre[to[i]]=u;	q.push(to[i]);
			}
		}
	}
}
signed main(){
	cin>>n>>m;
	for(int i=1,a,b;i<n;i++)	scanf("%d %d",&a,&b),add(a,b),add(b,a);
	for(int i=1;i<=m;i++)	scanf("%d",&c[i]);
	if(m==1)	return printf("YES\n%d\n",c[1]),0;
	bfs(c[1]);
	for(int i=2;i<=m;i++)	if(vis[c[i]]>mx)	id=c[i],mx=vis[c[i]];
	memset(vis,0,sizeof vis);	bfs(id); mx=0;
	for(int i=1;i<=m;i++)	if(vis[c[i]]>mx)	id1=c[i],mx=vis[c[i]];
	if((vis[id1]-1)&1)	return puts("NO"),0;
	int k=(vis[id1]-1)/2,x=id1;
	while(k--)	x=pre[x];
	queue<int> q;	q.push(x); d[x]=1;
	while(q.size()){
		int u=q.front();	q.pop();
		for(int i=head[u];i;i=nex[i]){
			if(!d[to[i]]){
				d[to[i]]=d[u]+1;	q.push(to[i]);
			}
		}
	}
	for(int i=1;i<=m;i++)	st.insert(d[c[i]]);
	if(st.size()==1)	printf("YES\n%d\n",x);
	else	puts("NO");
	return 0;
}