1 solutions

  • 0
    @ 2026-1-29 11:23:08
    #include<bits/stdc++.h>
    using namespace std;
    const int N=1e5+10,INF=0x3f3f3f3f;
    int n,m;
    typedef pair<int,int> PII;
    #define x first
    #define y second
    vector<PII> g[N];
    int dist[N];
    void dfs(int u,int father) //往下传递
    {
        for(auto k:g[u])
        {
            if(k.x==father) continue; //往回搜索
            dist[k.x]=dist[u]+k.y; //更新记录
            dfs(k.x,u); //继续往下传递
        }
    }
    int main()
    {
        cin>>n;
        for(int i=0;i<n-1;i++) //获取树
        {
            int a,b,c;
            cin>>a>>b>>c;
            g[a].push_back({b,c});
            g[b].push_back({a,c});
        }
        dfs(1,-1);
        int u=1; //找到最大距离
        for(int i=1;i<=n;i++)
        {
            if(dist[i]>dist[u])
            {
                u=i;
            }
        }
        dist[u]=0;
        dfs(u,-1);
        int v=1;//最远距离
        for(int i=1;i<=n;i++)
        {
            if(dist[i]>dist[v])
            {
                v=i;
            }
        }
        cout<<dist[v];
        return 0;
    }
    
    • 1

    Information

    ID
    2137
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    5
    Tags
    (None)
    # Submissions
    12
    Accepted
    6
    Uploaded By