526互联

Codeforces Round 903 (Div. 3) F. Minimum Maximum Distance（图论）

发布时间 2023-10-14 20:38:18作者: ikunhuaji

Codeforces Round 903 (Div. 3) F. Minimum Maximum Distance

思路

对标记点更新fg，从0开始进行bfs，更新d1为所有点到0的距离

获得到0最远的标记点L，从L开始bfs，更新d2为所有点到L的距离

获得距离L最远的标记点R，从R开始bfs，更新d3为所有点到R的距离

遍历所有点，这个点与标记点的最大距离一定为与L或R的距离

dis[i] = max ( d1[i] , d2[i] )

获得所有点的最小dis即可

#define int long long
#define ld long double

using namespace std;

int t;
queue<int>q;

void op()
{
	int n, k;
	cin >> n >> k;

	vector<bool>fg(n, 0);

	for (int i = 0; i < k; i++)
	{
		int x;
		cin >> x;
		fg[x - 1] = 1;
	}

	vector<vector<int>>head(n);

	for (int i = 0; i < n - 1; i++)
	{
		int u, v;
		cin >> u >> v;
		head[u-1].push_back(v-1);
		head[v-1].push_back(u-1);
	}
//bfs,d1为1到点的距离
	vector<int>d1(n, -1);

	q.push(0);

	d1[0] = 0;

	while (q.size())
	{
		int x = q.front();
		q.pop();
		for (auto y : head[x])
		{
			if (d1[y] != -1)continue;
			d1[y] = d1[x] + 1;
			q.push(y);
		}
	}
//
	int L = 0, maxn1 = -1;
	for (int i = 0; i < n; i++)
	{
		if (!fg[i])continue;
		if (d1[i] > maxn1)
		{
			L = i;
			maxn1 = d1[i];
		}
	}

//bfs,d2为点到L的距离
	vector<int>d2(n, -1);

	q.push(L);

	d2[L] = 0;

	while (q.size())
	{
		int x = q.front();
		q.pop();
		for (auto y : head[x])
		{
			if (d2[y] != -1)continue;
			d2[y] = d2[x] + 1;
			q.push(y);
		}
	}
//
	int R = 0, maxn2 = -1;
	for (int i = 0; i < n; i++)
	{
		if (!fg[i])continue;
		if (d2[i] > maxn2)
		{
			maxn2 = d2[i];
			R = i;
		}
	}

//bfs,d3为点到R的距离
	vector<int>d3(n, -1);

	q.push(R);

	d3[R] = 0;

	while (q.size())
	{
		int x = q.front();
		q.pop();
		for (auto y : head[x])
		{
			if (d3[y] != -1)continue;
			d3[y] = d3[x] + 1;
			q.push(y);
		}
	}
//
	vector<int>dis(n, -1);
	for (int i = 0; i < n; i++)
	{
		dis[i] = max(d2[i], d3[i]);
	}
	int minn = 0x3f3f3f3f;
	for(int i = 0; i < n; i++)
	{
		minn = min(minn, dis[i]);
	}
	cout << minn << endl;
}

signed main()
{
	cin >> t;
	while (t--)
	{
		op();
	}

	return 0;
}