LCA wa55pts 求助
查看原帖
LCA wa55pts 求助
723036
wmy18929355137楼主2024/5/30 21:20

玄关

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define N 400005

vector <int> G[N];
queue <int> Q;
int fa[N][64],n,m,q,dep[N],lg,mico[N]; //mico[i]:离i最近的传送点距离 

struct ccfgivemenopoints {
	void bfs() {
		memset(mico,0x3f,sizeof(mico));
		while (!Q.empty()) {
			int now = Q.front();
			Q.pop();
			for (auto u : G[now]) {
				if (mico[u] == 0x3f3f3f3f) {
					Q.push(u);
//					mico[u] = min(mico[now] + 1,mico[u]);
					mico[u] = mico[now] + 1;
				}
			}
		}
	}
	void dfs(int u,int pre) {
		dep[u] = dep[pre] + 1;
		fa[u][0] = pre;
		for (int i = 1; i <= lg; i++) {
			fa[u][i] = fa[fa[u][i - 1]][i - 1];
		}
		for (auto v : G[u]) {
			if (v != pre) {
				dfs(v,u);
			}
		}
	}
	int lca(int u,int v) {
		if (dep[u] < dep[v]) swap(u,v);
		for (int i = lg; i >= 0; i--) {
			if (dep[fa[u][i]] >= dep[v]) {
				u = fa[u][i];
			}
		}
		if (u == v) return u;
		for (int i = lg; i >= 0; i--) {
			if (fa[u][i] != fa[v][i]) {
				u = fa[u][i],v = fa[v][i];
			}
		}
		return fa[u][0];
	}
	void solve() {
		cin >> n >> m >> q;
		lg = log2(n) + 1;
		for (int i = 1; i < n; i++) {
			int x,y;
			cin >> x >> y;
			G[x].push_back(y);
			G[y].push_back(x);
		}
		for (int i = 1; i <= m; i++) {
			int x;
			cin >> x;
			mico[x] = 0;
			Q.push(x);
		}
		dfs(1,0);
		bfs();
		while (q--) {
			int x,y;
			cin >> x >> y;
			int ans = dep[x] + dep[y] - 2 * dep[lca(x,y)];
			ans = min(ans,mico[x] + mico[y]);
			//cout << dep[x] + dep[y] - 2 * dep[lca(x,y)] << endl;
			cout << ans << "\n";
		}
	}
};

signed main() {
	ccfgivemenopoints p;
	p.solve();
	return 0;
}
2024/5/30 21:20
加载中...