1 条题解

  • 0
    @ 2025-10-10 20:11:59

    C++ :

    #include<bits/stdc++.h>
    using namespace std;
    
    int n,a[1010][1010],dep[1010],fa[1010],width[1010];
    int maxw,maxd;//最大宽度和深度
    int u,v; 
    
    void dfs(int x,int fath){
    	fa[x] = fath;
    	dep[x] = dep[fath] + 1;
    	width[dep[x]]++;
    	maxd = max(maxd,dep[x]);//最大宽度 
    	maxw = max(maxw,width[dep[x]]);//最大深度 
    	
    	for(int i = 1;i <= n;i++){
    		if(a[x][i] && i != fath){
    			dfs(i,x);
    		}
    	}
    }
    
    int main()
    {
        cin>>n;
        int x,y;
        for(int i = 1;i <= n - 1;i++){
        	cin>>x>>y;
        	a[x][y] = 1;
        	a[y][x] = 1;
    	}
    	cin>>u>>v;
    	
    	dfs(1,0);
    	
    	cout<<maxd<<endl<<maxw<<endl; 
    	
    	//找到u和v的最近公共祖先
    	int tu = u,tv = v;
    	while(u != v){
    		if(dep[u] > dep[v]) u = fa[u];
    		else v = fa[v];
    	} 
    	
    	cout<<(dep[tu] - dep[u])*1 + dep[tv] - dep[u];
        return 0;
    }
     
    
    • 1

    信息

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