70pts求助
查看原帖
70pts求助
425330
Anahita楼主2022/3/17 20:47
#include <bits/stdc++.h>
using namespace std;
const int maxn = 500+5;
int head[maxn];
int cs[maxn];
int deep[maxn];
int d[maxn];
int k = 0;
int dmaxn = -1;
int wmaxn = -1;
int lcc[maxn][21];
struct note{
	int v;
	int next;
}e[maxn*2];
void add(int u,int v){
	e[k].v = v;
	e[k].next = head[u];
	head[u] = k++;
}
void dfs(int u,int fa){
	d[u] = d[fa]+1;
	dmaxn = max(dmaxn,d[u]);
	lcc[u][0] = fa;
	for(int i = 1;d[u]>=(1<<i);i++)
		lcc[u][i] = lcc[lcc[u][i-1]][i-1];
	for(int i = head[u];i!=-1;i = e[i].next){
		int v = e[i].v;
		if(v!=fa){
			dfs(v,u);
		}
	}
}
int lca(int a,int b){
	int ans = 0;
	if(d[b]>d[a]){
		for(int i = 20;i>=0;i--){
			if(d[a]<=d[b]-(1<<i)){
				b = lcc[b][i];
				ans+=(1<<i);
			}
		}
		if(a == b){
			return ans;
		} 
		for(int i = 20;i>=0;i--){
			if(lcc[a][i] == lcc[b][i]){
				continue;
			
			}
			else{
				a = lcc[a][i];
				b = lcc[b][i];
				if(i == 0){
					ans+=3;
				}
				else{
					ans+=3*(1<<i);
				} 
			}
		}
	}
	else if(d[a]>d[b]){
		for(int i = 20;i>=0;i--){
			if(d[b]<=(d[a]-(i<<1))){
				a = lcc[a][i];
				ans+=2*(1<<i);
			}
		}
		if(a == b){
			return ans;
		}
		for(int i = 20;i>=0;i--){
			if(lcc[a][i] == lcc[b][i]){
				continue;
			}
			else{
				a = lcc[a][i];
				b = lcc[b][i];
				if(i == 0){
					ans+=3;
				}
				else{
					ans+=3*(1<<i);
				} 
			}
		}
	
	}
	else{
		if(a == b){
			return ans;
		}
		for(int i = 20;i>=0;i--){
			if(lcc[a][i] == lcc[b][i]){
				continue;
			}
			else{
				a = lcc[a][i]; 
				b = lcc[b][i];
				if(i == 0){
					ans+=3;
				}
				else{
					ans+=3*(1<<i);
				} 
			}
		}
	
	}
	return ans+3;	
}
int n;
int main(){
	memset(head,-1,sizeof(head));
	cin>>n;
	for(int i = 1;i<n;i++){
		int t1,t2;
		scanf("%d%d",&t1,&t2);
		add(t1,t2);
		add(t2,t1);
	}
	int t1,t2;
	dfs(1,0);
	scanf("%d%d",&t1,&t2);
	for(int i = 1;i<=n;i++){
		cs[d[i]]++;
	}
	for(int i = 1;i<=dmaxn;i++){
		wmaxn = max(wmaxn,cs[i]);
	}
	cout<<dmaxn<<endl<<wmaxn<<endl;

	cout<<lca(t1,t2);
	return 0;
} 

求dalao们帮我看看,哪里出了问题

70分,#1,#6,#9出了问题

2022/3/17 20:47
加载中...