C++(g++ 7.5.0) 解法, 执行用时: 424ms, 内存消耗: 39888K, 提交时间: 2022-09-27 22:36:54

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
int n;
int A,B,C;
vector<int>G[200005];
int fa[200005][20];
int dep[200005];
int yszc[200005],yy[200005];
void dfs(int u,int f);
int Ask_lca(int a,int b);
int main() {
	int i,j,k;
	int oo,pp,qq;
	scanf("%d",&n);
	for(i=1;i<n;i++) {
		int u,v;
		scanf("%d%d",&u,&v);
		G[u].pb(v);
		G[v].pb(u);
	}
	scanf("%d%d%d",&A,&B,&C);
	dep[A]=0;
	fa[A][0]=A;
	dfs(A,A);
	for(i=1;i<=19;i++)
		for(j=1;j<=n;j++)
			fa[j][i]=fa[fa[j][i-1]][i-1];
	int wwxB=yszc[B],B1=yy[B];
	for(i=1;i<=n;i++) {
		oo=Ask_lca(i,B);
		if(dep[B]-dep[oo]<dep[oo]) {
			pp=dep[i];
			if(pp>wwxB) {
				wwxB=pp;
				B1=i;
			}
		}
	}
	int wwxC=wwxB;
	oo=Ask_lca(yy[C],B1);
	wwxC+=dep[B1]+yszc[C]-2*dep[oo];
	for(i=1;i<=n;i++) {
		oo=Ask_lca(B1,i);
		qq=Ask_lca(C,oo);
		if(dep[C]+dep[oo]-2*dep[qq]<dep[B1]-dep[oo]+wwxB)
			wwxC=max(wwxC,wwxB+dep[i]+dep[B1]-2*dep[oo]);
	}
	printf("%d %d\n",wwxB,wwxC);
    return 0;
}
void dfs(int u,int f) {
	yszc[u]=dep[u];
	yy[u]=u;
	for(auto v:G[u]) {
		if(v==f)
			continue;
		fa[v][0]=u;
		dep[v]=dep[u]+1;
		dfs(v,u);
		if(yszc[v]>yszc[u]) {
			yszc[u]=yszc[v];
			yy[u]=yy[v];
		}
	}
}
int Ask_lca(int a,int b) {
	int i,j,k;
	if(dep[a]<dep[b])
		swap(a,b);
	for(i=19;i>=0;i--)
		if(dep[fa[a][i]]>=dep[b])
			a=fa[a][i];
	if(a==b)
		return a;
	for(i=19;i>=0;i--) {
		if(fa[a][i]!=fa[b][i]) {
			a=fa[a][i];
			b=fa[b][i];
		}
	}
	return fa[a][0];
}

C++(clang++ 11.0.1) 解法, 执行用时: 170ms, 内存消耗: 20920K, 提交时间: 2022-09-25 21:29:50

#include<bits/stdc++.h>
using namespace std;
const int M=2e5+7;
int n,fa[M],dep[M],a,b,c,ans;
vector<int> vec[M];
void dfs(int nw,int faa,int dp){
	dep[nw]=dp,fa[nw]=faa;
	for(auto i:vec[nw])
		if(i!=faa) dfs(i,nw,dp+1);
}
void get_right_pos(int& x,int cnt=0){
	while(cnt!=0){
		if(fa[x]!=a) x=fa[x];
		cnt--;
	}
	int xx=x;
	while(fa[x]!=a) x=fa[x],cnt++;
	cnt/=2;
	while(cnt-- && fa[xx]!=0) xx=fa[xx];
	x=xx;
}
pair<int,int> wk(int x){
	int ans=0,id;
	if(vec[x].size()==1 && fa[x]!=0)
		return {dep[x],x};
	for(auto i:vec[x]) if(i!=fa[x]){
		auto now=wk(i);
		if(now.first>ans)
			ans=now.first,id=now.second;
	}
	return {ans,id};
}
int main(){
	scanf("%d",&n);
	for(int i=1,x,y;i<n;i++)
		scanf("%d%d",&x,&y),
		vec[x].push_back(y),
		vec[y].push_back(x);
	scanf("%d%d%d",&a,&b,&c);
	dfs(a,0,0);
	get_right_pos(b);
	auto anss=wk(b);
	printf("%d ",anss.first);
	a=anss.second;
	dfs(a,0,0);
	get_right_pos(c,anss.first);
	auto ansss=wk(c);
	printf("%d",anss.first+ansss.first);
	return 0;
}