LCA模板

逃离我推掉我的手 2022-09-05 00:06 112阅读 0赞

LCA

LCA ver1
    int LCA(int u, int v) {
    	if (D[u] < D[v])swap(u, v);//保证D[u]>D[v]
    	//2^L 是不小与树的高度的最小的2的幂,其中L=ceil(log2(n));
    	for (int h = L; h >= 0; h--)//让u倍增往上爬，对于D(u)-D(v)的二进制中所以的2^h,执行u=UP[u][h]
    		if (D[UP[u][h]] >= D[v])
    			u = UP[u][h];
    	if (u == v)return u;//向上爬之后D(u)=D(v)
    	for (int h = L; h >= 0; h--)//让u,v同时往上爬，最后到达最近公共祖先
    		if (UP[u][h] != UP[v][h])
    			u = UP[u][h], v = UP[v][h];
    	return UP[u][0];
    }
    
    //ver2
    using namespace std;
    const int maxn = 5e5 + 10;
    const int len = 33;
    int Tin[maxn], Tout[maxn], timer;
    int UP[maxn][len];
    int L = 20;
    int D[maxn];
    vector<int> G[maxn];
    //LCA预处理
    void dfs(int u, int fa) {
    
    	UP[u][0] = fa;	D[u] = D[fa] + 1;
    	Tin[u] = ++timer;
    	for (int i = 1; (1 << i) <= D[u]; i++)
    		UP[u][i] = UP[UP[u][i - 1]][i - 1];
    	for (auto v : G[u]) {
    		if (v == fa)continue;
    		dfs(v, u);
    	}
    	Tout[u] = timer;
    }
    bool isAncestor(int u, int v) { return Tin[u] <= Tin[v] && Tout[u] >= Tout[v]; }
    
    
    int LCA(int u, int v) {
    	if (D[u] > D[v])return LCA(v, u);//保证D(u)<=D(v)
    	if (isAncestor(v, u))return v;
    	if (isAncestor(u, v))return u;//如果u是v的祖先,直接返回u即可。
    	//否则UP(u,i)不是v的祖先,就沿着u往上爬2^i级，直到爬到LCA(u,v)子节点为止。
    	for (int i = ceil(log2(D[u])); i >= 0; --i)
    		if (UP[u][i] && !isAncestor(UP[u][i], v))//有零的影响
    			u = UP[u][i];
    	return UP[u][0];
    }
    
    
    int n, m, rt;
    
    int main()
    {
    
    	ios::sync_with_stdio(false);
    	cin >> n >> m >> rt;
    	for (int i = 1; i < n; i++)
    	{
    		int a, b; cin >> a >> b;
    		G[a].push_back(b);
    		G[b].push_back(a);
    	}
    	dfs(rt, rt);
    	while (m--)
    	{
    		int a, b;
    		cin >> a >> b;
    		cout << LCA(a, b) << endl;
    	}
    	return 0;
    }