1 条题解

  • 0
    @ 2025-10-10 20:12:00

    C++ :

    #include <bits/stdc++.h>
    using namespace std;
    
    const int N = 100010;
    /*
    	fa:每个元素的父元素 dep:每个元素的深度
    	pre:每个点的最后一条边
    	k:边的数量
    */
    int fa[N],dep[N],pre[N],k;
    
    struct node {
    	int from,to,next;
    } a[N*2];
    
    int x,y,t1,t2,n;
    
    //加边
    void add(int u,int v) {
    	k++;
    	a[k].from = u;
    	a[k].to = v;
    	a[k].next = pre[u];
    	pre[u] = k;
    }
    
    //深搜求元素的父和深度
    void dfs(int x,int fath) {
    	fa[x] = fath;
    	dep[x] = dep[fath] + 1;
    
    	for(int i = pre[x]; i != 0; i = a[i].next) {
    		if(a[i].to != fath) {
    			dfs(a[i].to,x);
    		}
    	}
    }
    
    int main() {
    	cin>>n;
    	//读入关系
    	for(int i = 1; i <= n - 1; i++) {
    		cin>>x>>y;
    		add(x,y);
    		add(y,x);
    	}
    
    	dfs(1,0);//求每个点的父及深度
    
    	x = 1;
    	for(int i = 2; i <= n; i++) {
    		if(dep[i] > dep[x]) x = i;
    	}
    
    	dfs(x,0);
    	y = 1;
    	int ans = 0;//直径
    	for(int i = 2; i <= n; i++) {
    		if(dep[i] > dep[y]) y = i;
    	}
    
    //	cout<<x<<" "<<y<<endl<<dep[y] - 1<<endl;
    	//从y开始向上爬到一半的深度,就是直径
    	//中点只有1个,爬一半的距离就是中点
    	int d = dep[y];
    	if(d%2 != 0) {
    		for(int i = 1; i <= d / 2; i++) {
    			y = fa[y];
    		}
    		cout<<y;
    	} else {
    		//中点有2个,爬一半的距离,以及一半距离+1
    		for(int i = 1; i <= d / 2 - 1; i++) y = fa[y];
    		if(y < fa[y]) cout<<y<<" "<<fa[y];
    		else cout<<fa[y]<<" "<<y;
    		
    	}
    	
    
    	return 0;
    }
    
    
    • 1

    信息

    ID
    1092
    时间
    1000ms
    内存
    512MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者