TLE 8,9求调
查看原帖
TLE 8,9求调
1229738
SparkingDaydream楼主2024/11/21 01:08
#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int N=5e5+10;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return x*f;
}


vector<int>e[N];
int dep[N];
int fa[N][22];
void solve(){
	int n=read(),m=read();
	for(int i=1;i<=n-1;i++){
		int a=read(),b=read();
		e[a].push_back(b);
		e[b].push_back(a);
	}

	vector<int>dep(n+1,0);
	auto dfs=[&](auto&&self,int x,int father)->void{
		dep[x]=dep[father]+1;
		fa[x][0]=father;
		for(int i=1;i<=18;i++)
			fa[x][i]=fa[fa[x][i-1]][i-1];
		for(auto y:e[x])
			if(y!=father) self(self,y,x);
	};
	dep[0]=-1;
	dfs(dfs,1,0);
	auto lca=[&](int x,int y)->int{
		if(dep[x]<dep[y]) swap(x,y);
		for(int i=18;i>=0;i--)
			if(dep[fa[x][i]]>=dep[y]) x=fa[x][i];
		if(x==y) return x;
		for(int i=18;i>=0;i--)
			if(fa[x][i]!=fa[y][i])
				x=fa[x][i],y=fa[y][i];
		return fa[x][0];
	};

	for(int i=1;i<=m;i++){
		int a=read(),b=read(),c=read();
		if(a==b&&b==c){
			cout<<a<<" "<<0<<endl;
		}else{
			int rt[4];
			rt[1]=lca(a,b),rt[2]=lca(a,c),rt[3]=lca(b,c);
			auto cmp=[&](int x,int y)->bool{
				int sum1=
					dep[a]+dep[x]-2*dep[lca(a,x)]+
					dep[b]+dep[x]-2*dep[lca(b,x)]+
					dep[c]+dep[x]-2*dep[lca(c,x)];
				int sum2=
				    dep[a]+dep[y]-2*dep[lca(a,y)]+
					dep[b]+dep[y]-2*dep[lca(b,y)]+
					dep[c]+dep[y]-2*dep[lca(c,y)];
				return sum1<sum2;
			};
			sort(rt+1,rt+4,cmp);
			int ans=
				dep[a]+dep[rt[1]]-2*dep[lca(a,rt[1])]+
				dep[b]+dep[rt[1]]-2*dep[lca(b,rt[1])]+
				dep[c]+dep[rt[1]]-2*dep[lca(c,rt[1])];
			cout<<rt[1]<<" "<<ans<<endl;
		}
	}
	
}
signed main(){
	solve();
	return 0;
}
2024/11/21 01:08
加载中...