树带权重心

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+5;
struct graph{
    int v,w;
};
vector<graph>g[N];
int n,up[N],down[N];
void dfs(int u,int last){
    for(auto [v,w]:g[u]){
        if(v!=last){
            dfs(v,u),down[u]=max(down[u],down[v]+w);
        }
    }
}
int calc(int u,int v,int last){//v往上到u 不到v 从u往下
    int ret=0;
    for(auto [vv,w]:g[u]){
        if(vv!=v&&vv!=last){
            ret=max(ret,w+down[vv]);
        }
    }
    return ret;
}
void dfs_(int u,int last){
    for(auto [v,w]:g[u]){
        if(v!=last){
            up[v]=max(up[u]+w,w+calc(u,v,last)),dfs_(v,u);
        }
    }
}
int main(){
    cin>>n;
    for(int i=1,u,v,w;i<n;i++){
        cin>>u>>v>>w,g[u].push_back({v,w}),g[v].push_back({u,w});
    }
    dfs(1,1),dfs_(1,1);
    int ans=-1;
    for(int i=1;i<=n;i++){
        if(ans==-1){
            ans=max(down[i],up[i]);
        }
        else{
            ans=min(ans,max(down[i],up[i]));
        }
    }
    cout<<ans;
}

我觉得这是O(n^2)的 在Acwing交了一发 跑的飞快 而n=1e4 Acwing的机子慢不该跑过 chatgpt说是O(n)的 那复杂度是否是O(n^2)的