大佬们,救救孩子们吧(全TLE)
查看原帖
大佬们,救救孩子们吧(全TLE)
378996
UncleSam_Died楼主2021/7/21 21:17
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5*1e5;//定义1个常量 
const int inf=1e9;
int n,m; 
int u,v;
struct edge{//结构体 
	int v,w,next;
}tu[MAXN];
int head[MAXN],vis[MAXN],dis[MAXN],lg[MAXN],depth[MAXN],f[MAXN][22],ce,dis_kk,dis_fk,dis_me,xy_kk,xy_kf,xy_me,ans;//定义head数组,用于链式前向星存图  ans存储最小花费 
//定义adde函数,使用链式前向星存图 
void adde(int u,int v,int w){
	tu[++ce].v=v;
	tu[ce].w=w;
	tu[ce].next=head[u];
	head[u]=ce;
}
void dfse(int now,int fath){
	f[now][0]=fath;
	depth[now]=depth[fath]+1;
	for(int i=1;i<=lg[depth[now]];i++){
		f[now][i]=f[f[now][i-1]][i-1];
	}
	for(int i=head[now];i;i=tu[i].next){
		if(tu[i].v!=fath){
			dfse(tu[i].v,now);
		}
	}
}
bool is(int vis[],int x,int end){
	if(x==end){
		return true;
	}
	for(int i=head[x];i;i=tu[i].next){
		if(!vis[tu[i].v]){
			vis[tu[i].v]=1;
			is(vis,tu[i].v,end);
		}
	}
	return false;
}
int vise[MAXN]; 
int fis(int vis[],int x,int end,int vise[]){
	if(is(vis,x,end)){
		return x;
	}
	for(int i=head[u];i;i=tu[i].next){
		if(!vise[tu[i].v]){
			vise[tu[i].v]=1;
			fis(vis,tu[i].v,end,vise);
		}
	}
}
int LCA(int a,int b,int end){
	memset(vis,0,sizeof(vis));
	memset(depth,0,sizeof(depth));
	memset(f,0,sizeof(f));
	vis[a]=1;vis[b]=1;
	if(depth[a]<depth[b]){
		swap(a,b);
	}
	while(depth[a]>depth[b]){
		a=f[a][lg[depth[a]-depth[b]]-1];
	}
	if(a==b){
		if(is(vis,a,end)){
			return a;
		}else{
			memset(vise,0,sizeof(vise));
			return fis(vis,a,end,vise);
		}
	}
	for(int i=lg[depth[a]-1];i>=0;i--){
		if(f[a][i]!=f[b][i]){
			a=f[a][i];
			b=f[b][i];
		}
		else{
			continue;
		}
	}
	if(!is(vis,f[a][0],end)){
		memset(vise,0,sizeof(vise));
		return fis(vis,a,end,vise);
	}
	return f[a][0];
}
//dfs函数,计算三人相互间的距离
int dfs(int x,int y){
	queue<int> q;
	//初始化dis数组(记录距离)
	memset(dis,inf,sizeof(dis));//初始化距离为极大值,用于后方松弛操作找最短路 
	//初始化vis数组,标记所有点为没被走过 
	memset(vis,0,sizeof(vis));
	//将出发点的距离标为0 
	dis[x]=0;
	//将出发点标为被走过的
	vis[x]=1;
	//将出发点入队
	q.push(x);
	//当队列不为空时,进行操作 
	while(!q.empty()){
		int t=q.front();//获取当前的对首元素,即上一次操作到达的点
		q.pop();//将该点出队
		//访问所有与该点相连的点 
		for(int i=head[t];i;i=tu[i].next){
			int v=tu[i].v;//记录下一步将走的点的编号
			int w=tu[i].w;//记录下一步将走的边的权值
			if(dis[v]>dis[t]+w){//松弛操作,判断可不可以通过该点使得路程更短
				dis[v]=dis[t]+w;//更新距离
				if(!vis[v]){//判断当前这个点有没有走过 
					vis[v]=1;//将当前点标记为走过
					q.push(v);//将该点入队 
				}	
			} 
		}
		return dis[y];//返回x点到y点的最短距离 
	}
} 
void out(int x,int y,int z){
	//x:小可可所在点的编号 y:小可可朋友所在点的编号 z:我所在的编号 
	//dis_kk表示小可可和小可可的朋友的距离
	//dis_fk表示小可可的朋友和我的距离
	//dis_me表示我和小可可的距离
	dis_kk=dfs(x,y);
	dis_fk=dfs(y,z);
	dis_me=dfs(z,x); 
	int maxx=max(dis_kk,max(dis_fk,dis_me));//maxx存储距离最远的两个点间的距离
	ans+=maxx;
	if(maxx=dis_kk){
		dfse(1,0);
		int lca=LCA(y,z,x);
		ans+=dfs(lca,z);
		cout<<lca<<' '<<ans<<endl;
	}else if(maxx=dis_fk){
		dfse(1,0);
		int lca=LCA(x,z,y);
		ans+=dfs(lca,x);
		cout<<lca<<" "<<ans<<endl;
	}else{
		dfse(1,0);
		int lca=LCA(x,y,z);
		ans+=dfs(lca,y);
		cout<<lca<<" "<<ans<<endl;		
	}
	
}
int main(){
	cin>>n>>m;//输入n,m,n:点的个数,一共有n-1条边。m:询问的次数 
	for(int i=1;i=n-1;i++){
		cin>>u>>v;//输入相连的两个点的编号 
		adde(u,v,1);//调用adde()函数,并将每条边的权值设为1 
		adde(v,u,1);//因为是无向图,所以调用两次,建一条反向的边 
	}
	for(int i=1;i<=m;i++){
		cin>>xy_kk>>xy_kf>>xy_me;//输入当前小可可、小可可的朋友以及我所在点的编号 
		out(xy_kk,xy_kf,xy_me);//调用out()函数输出集合的点及最小花费 
	}
	return 0;
}

2021/7/21 21:17
加载中...