1 条题解

  • 2
    @ 2023-7-15 8:59:46
    /*****************************************
    Note:
    ******************************************/
    #include <queue>
    #include <math.h>
    #include <stack>
    #include <stdio.h>
    #include <iostream>
    #include <vector>
    #include <iomanip>
    #include <string.h>
    #include <algorithm>
    using namespace std;
    #define LL long long
    const int N = 1e6 + 10;
    const int INF = 0x3f3f3f3f;
    int head[N] , to[N] ,  ne[N] , id;
    int f[N] , s[N] , maxx;
    void add(int x, int y)
    {
    	to[++id] = y , ne[id] = head[x] , head[x] = id;
    	to[++id] = x , ne[id] = head[y] , head[y] = id;
    }
    void dfs1(int u , int fa)
    {
    	f[u] = 1 , s[u] = 0;
    	int ans = 0;
    	for(int i = head[u] ; i ; i = ne[i])
    	{
    		int v = to[i];
    		if(v == fa)	continue;
    		dfs1(v , u);
    		if(f[v] + 1 > f[u])
    		{
    			s[u] = f[u];
    			f[u] = f[v] + 1;
    		}
    		else if(f[v] + 1 > s[u])
    			s[u] = f[v] + 1 ;
    	}
    }
    void dfs2(int u , int fa , int dis)
    {
    	for(int i = head[u] ; i ;i = ne[i])
    	{
    		int v = to[i];
    		if(v == fa)	continue;
    		if(f[u] == f[v]+1)
    			dfs2(v,u,max(dis+1,s[u] + 1));
    		else 
    			dfs2(v,u,max(dis+1,f[u] + 1));
    	}
    	if(dis > f[u])
    		s[u] = f[u] , f[u] = dis;
    	else if(dis > s[u])
    		s[u] = dis; 
    	maxx = max(f[u] + s[u] , maxx);
    
    }
    int main()
    {
    	int n;
    	cin >> n;
    	for(int i = 1; i < n ; i++)
    	{
    		int x,y;
    		cin >> x >> y;
    		add(x + 1, y + 1);
    	}
    	dfs1(1,0);
    	dfs2(1,0 ,0);
    	for(int i = 1; i <= n ; i++)
    	{
    		if(f[i] + s[i] == maxx)
    			cout << i - 1<< endl;
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    476
    时间
    1000ms
    内存
    512MiB
    难度
    4
    标签
    递交数
    58
    已通过
    28
    上传者