就是求一个树的直径 然后再在这个路径中找一点
emmmmmm大概那个意思
就这样吧emmmm 详见代码
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #include<cstring> 5 #include<cmath> 6 #include<stack> 7 #include<algorithm> 8 using namespace std; 9 #define ll long long 10 #define rg register 11 const int N=200000+5,P=9901,inf=0x3f3f3f3f; 12 int n,m,s;ll ans=0,maxl,sa,mm=0; 13 template <class t>void rd(t &x) 14 { 15 x=0;int w=0;char ch=0; 16 while(!isdigit(ch)) w|=ch=='-',ch=getchar(); 17 while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); 18 x=w?-x:x; 19 } 20 21 int head[N],tot=0; 22 struct edge{ 23 int v,nxt;ll w; 24 }e[N<<1]; 25 void add(int u,int v,ll w){ 26 e[++tot].v=v,e[tot].w=w,e[tot].nxt=head[u],head[u]=tot; 27 } 28 29 ll a[N],b[N]; 30 void dfs(int u,int fa,ll d[]) 31 { 32 // if(d[u]>maxl) sa=u,maxl=d[u]; 33 for(rg int i=head[u];i;i=e[i].nxt) 34 { 35 int v=e[i].v,w=e[i].w; 36 if(v==fa) continue; 37 d[v]=d[u]+w; 38 if(d[v]>maxl) sa=v,maxl=d[v]; 39 dfs(v,u,d); 40 } 41 } 42 43 int main() 44 { 45 // freopen("in.txt","r",stdin); 46 //freopen("nocows.out","w",stdout); 47 memset(a,0,sizeof(a)); 48 rd(n),rd(m); 49 int u,v;ll w; 50 for(rg int i=1;i<=m;++i) 51 { 52 rd(u),rd(v),rd(w); 53 add(u,v,w),add(v,u,w); 54 } 55 dfs(1,0,a);maxl=0; 56 memset(a,0,sizeof(a)); 57 dfs(sa,0,a);ans=maxl,maxl=0; 58 dfs(sa,0,b); 59 for(rg int i=1;i<=n;++i) 60 mm=max(mm,min(a[i],b[i])); 61 printf("%lld",mm+ans); 62 return 0; 63 }