25pts求调
查看原帖
25pts求调
1369607
luckyqwq楼主2024/6/28 14:23
#include <bits/stdc++.h>//显然本题中是一棵树
#define int long long
const int N = 2e5 + 10;
using namespace std;
inline int read(){
	int r = 0,w = 1;
	char c = getchar();
	while (c < '0' || c > '9'){
		if (c == '-'){
			w = -1;
		}
		c = getchar();
	}
	while (c >= '0' && c <= '9'){
		r = (r << 3) + (r << 1) + (c ^ 48);
		c = getchar();
	}
	return r * w;
}
int dis[N];
vector < int > e[N];
queue < int > q;
void add(int x, int y) {
	e[x].push_back(y);
	e[y].push_back(x);
}
int n, m, qq, depth[N], fa[N][25], lg[N];
void dfs(int now, int fath) {
	fa[now][0] = fath; depth[now] = depth[fath] + 1;
	for(int i = 1; i <= lg[depth[now]]; ++i)
		fa[now][i] = fa[fa[now][i - 1]][i - 1];
	for(int v : e[now])
		if(v != fath) dfs(v, now);
}
int lca(int x, int y) {
	if(depth[x] < depth[y]) swap(x, y);
	while(depth[x] > depth[y])
		x = fa[x][lg[depth[x] - depth[y]] - 1];
	if(x == y) return x;
	for(int k = lg[depth[x]] - 1; k >= 0; --k)
		if(fa[x][k] != fa[y][k])
			x = fa[x][k], y = fa[y][k];
	return fa[x][0];
}
void bfs()
{
	while(q.size())
	{
		int u = q.front();
		q.pop();
		for (auto v : e[u])
		{
			if(dis[v] == 0x3f)
			{
				dis[v] = dis[u] + 1;
				q.push(v);
			}
		}
	}
}
signed main() {
	cin >> n >> m >> qq;
	for(int i = 1; i < n; ++ i) {
		int x, y; x = read(), y = read();
		add(x, y); add(y, x);
	}
	memset(dis, 0x3f, sizeof dis);
	for (int i = 1;i <= m; ++ i)
	{
		int x;
		x = read();
		dis[x] = 0;
		q.push(x);//初始化传送门 
	}
	for(int i = 1; i <= n; ++ i){
		lg[i] = lg[i >> 1] + 1;
	}
	dfs(1, 0);
	bfs();
	while (qq --)
	{
		int x, y;
		x = read(), y = read();
		cout << min(depth[x] + depth[y] - 2 * depth[lca(x, y)], dis[x] + dis[y]) << "\n";//从传送门和LCA的方法中取小值 
	}
	return 0;
}
/*
显然,在 k = 0 的情况下,只要求出两点到最近 LCA 的距离和即可。
k != 0 显然要根据贪心策略,找到点 u 最近的传送门,和点 v 最近的传送门,两个距离相加,与前面 LCA 的情况取小值 
*/

TLE + WA,调不出来,LCA + bfs。

2024/6/28 14:23
加载中...