1 条题解

  • 0
    @ 2025-5-22 15:18:14
    #include<bits/stdc++.h>
    #include<vector>
    #include<queue>
    #include<algorithm>
    using namespace std;
    int n,u,v,w,k,sum;
    struct edge{int x,y;};
    vector<edge> a[200001];
    int bfs(int s){
    	int maxn = s;
    	int tr[100002];
    	memset(tr, 0 ,sizeof(tr));
    	tr[s] = 1;
        queue<int> q;
        q.push(s);
        while(!q.empty()){
            int l = q.front();
            q.pop();
            for(int i = 0;i < a[l].size();i++){
                if(tr[a[l][i].x] == 0){
                    q.push(a[l][i].x);
                    tr[a[l][i].x] = tr[l] + a[l][i].y;
                    if(tr[maxn] < tr[a[l][i].x]){
                    	maxn = a[l][i].x;
    				}
                }
            }
        }
        sum = tr[maxn] - 1;
        return maxn;
    }
    int main(){
        scanf("%d",&n);
        k = n;
        while(--n){
            scanf("%d%d%d",&u,&v,&w);
            a[u].push_back({v,w});
            a[v].push_back({u,w});
        }
        bfs(bfs(1));
        printf("%d",sum);
        return 0;
    }
    

    两次bfs就可以了,easy

    • 1

    信息

    ID
    8346
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    递交数
    16
    已通过
    5
    上传者