寻找

C++14(g++5.4) 解法, 执行用时: 331ms, 内存消耗: 20448K, 提交时间: 2019-04-15 16:06:46

#include<bits/stdc++.h>
using namespace std;
const int MAX=2e5+10;
const int MOD=1e9+7;
const double PI=acos(-1.0);
typedef long long ll;
vector<int>e[MAX];
int nex[MAX][21];
int d[MAX];
void dfs(int k,int fa,int dep)
{
    d[k]=dep;
    nex[k][0]=fa;
    for(int i=1;i<=20;i++)nex[k][i]=nex[nex[k][i-1]][i-1];
    for(int i=0;i<e[k].size();i++)
    {
        int nex=e[k][i];
        if(nex==fa)continue;
        dfs(nex,k,dep+1);
    }
}
int LCA(int x,int y)
{
    if(x==y)return x;
    if(d[x]>d[y])swap(x,y);
    for(int i=20;i>=0;i--)
    {
        if(d[x]<d[y]&&d[nex[y][i]]>=d[x])y=nex[y][i];
    }
    for(int i=20;i>=0;i--)
    {
        if(nex[x][i]!=nex[y][i])
        {
            x=nex[x][i];
            y=nex[y][i];
        }
    }
    if(x!=y)return nex[x][0];
    return x;
}
int main(){
	int n;
	scanf("%d",&n);
	int u,v;
	for(int i=0;i<n-1;i++){
		scanf("%d%d",&u,&v);
		e[u].push_back(v);
		e[v].push_back(u);
	} 
	dfs(1,0,1);
	int q;
	scanf("%d",&q);
	while(q--){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		int A=LCA(a,b);
		int B=LCA(a,c);
		int C=LCA(b,c);
		int D=LCA(A,c);
		if(d[D]<d[A])
			printf("%d\n",A);
		else if(d[B]>d[C])
			printf("%d\n",B);
		else printf("%d\n",C);
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 323ms, 内存消耗: 18296K, 提交时间: 2019-04-16 21:53:28

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
int dep[N],Fa[N][22],n,q;
vector<int>G[N];
void dfs(int u,int fa) {
	dep[u]=dep[fa]+1;
	Fa[u][0]=fa;
	for(int i=1; (1<<i)<=dep[u]; i++) Fa[u][i]=Fa[Fa[u][i-1]][i-1];
	for(auto &v:G[u]) {
		if(v==fa) continue;
		dfs(v,u);
	}
}
int lca(int x,int y) {
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=20; i>=0; i--) if((1<<i)<=dep[x]-dep[y]) x=Fa[x][i];
	if(x==y) return x;
	for(int i=20; i>=0; i--) if(Fa[x][i]!=Fa[y][i]) x=Fa[x][i],y=Fa[y][i];
	return Fa[x][0];
}
int dis(int x,int y) {
	return dep[x]+dep[y]-2*dep[lca(x,y)];
}
int main(int argc, char const *argv[]) {
	scanf("%d",&n);
	for(int i=0; i<n-1; i++) {
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}
	dfs(1,0);
	scanf("%d",&q);
	while(q--) {
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		int ab=lca(a,b);
		int ac=lca(a,c);
		int bc=lca(b,c);
		int mi=1e9+7;
		mi=min(dep[ac],dep[bc]);
		if(mi<dep[ab]) printf("%d\n", ab);
		else printf("%d\n",dep[c]-dep[ac]<dep[c]-dep[bc] ? ac:bc);
	}
	return 0;
}

详情