1 条题解

  • 0
    @ 2025-10-8 16:58:41
    #include<bits/stdc++.h>
    using namespace std;
    const int N=2e5+10;
    vector<int>G[N];
    int ans,d1[N],d2[N];//d1[i]和d2[i]分别在dfs1和dfs2中有不同含义 
    /*dfs1中含义:
    d1[i]表示以点i为出发点向下的最长路径;
    d2[i]表示以点i为出发点向下的第二长路径;
    */
    void dfs1(int x,int fa)
    {
        for(auto y:G[x])if(y!=fa)
    	{
            dfs1(y,x);
            if(d1[y]+1>d1[x])      d2[x]=d1[x],d1[x]=d1[y]+1;
            else if(d1[y]+1>d2[x]) d2[x]=d1[y]+1;   
        }
    	ans=max(ans,d1[x]+d2[x]);
    }
    /*dfs2中含义:
    d1[i]表示以点i为出发点(可向上或向下)的最长路径;
    d2[i]表示以点i为出发点(可向上或向下)的第二长路径;
    */
    
    void dfs2(int x,int fa)
    {
        for(auto y:G[x])if(y!=fa) {
            if(d1[x]!=d1[y]+1)//具有换根的意味 
            {
                if(d1[x]+1>d1[y])      d2[y]=d1[y],d1[y]=d1[x]+1;
                else if(d1[x]+1>d2[y]) d2[y]=d1[x]+1;    
            }else{
                if(d2[x]+1>d1[y])      d2[y]=d1[y],d1[y]=d2[x]+1;
                else if(d2[x]+1>d2[y]) d2[y]=d2[x]+1;  
            }
            dfs2(y,x);
        }   
    }
    int main()
    {
        int n;scanf("%d",&n);
        for(int i=1,x,y;i<=n-1;i++)
        {
            scanf("%d %d",&x,&y); x++,y++;
            G[x].push_back(y); G[y].push_back(x);
        }
        memset(d1,0,sizeof(d1)); memset(d2,0,sizeof(d2));
        dfs1(1,0);
        dfs2(1,0);
        for(int i=1;i<=n;i++)if(d1[i]+d2[i]==ans) printf("%d\n",i-1);
        return 0;
    }
    
    • 1

    *【树形DP:树的直径】判断点是否在树的最长路径上[旅游规划]

    信息

    ID
    1802
    时间
    1000ms
    内存
    512MiB
    难度
    7
    标签
    递交数
    23
    已通过
    9
    上传者