昨晚被欧老师D得怀疑人生。。。
再次表扬一下自己2A(记错了数据范围。。。)
为什么我的感觉就是打了个暴力。。。
两个dfs处理出树的直径，确定了两点
然后接着暴力找剩下那个点。
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; struct node { int x,y,next;LL d; }a[410000];int len,last[210000]; void ins(int x,int y,LL d) { len++; a[len].x=x;a[len].y=y;a[len].d=d; a[len].next=last[x];last[x]=len; } int L,R;LL dis; void getL(int x,int fr,LL d) { if(d>dis)dis=d,L=x; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=fr) getL(y,x,d+a[k].d); } } void getR(int x,int fr,LL d) { if(d>dis)dis=d,R=x; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=fr) getR(y,x,d+a[k].d); } } bool v[210000];LL dis2; void findthird(int x,int fr,LL d) { if(dis2<d)dis2=d; for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=fr&&v[y]==false) findthird(y,x,d+a[k].d); } } int hp,h[210000],p[210000];bool bk; void dfs(int x,int fr) { if(bk==true)return ; if(x==R) { bk=true; LL mmax=0,lsum=0,rsum=dis; for(int i=1;i<=hp;i++) { lsum+=h[i],rsum-=h[i]; dis2=0;findthird(p[i],0,0); mmax=max(mmax,dis2+min(lsum,rsum)*2+max(lsum,rsum)); } printf("%lld ",mmax); return ; } for(int k=last[x];k;k=a[k].next) { int y=a[k].y; if(y!=fr) { hp++; h[hp]=a[k].d; p[hp]=y; v[y]=true; dfs(y,x); v[y]=false; p[hp]=0; h[hp]=0; hp--; } } } int main() { int n,m; scanf("%d%d",&n,&m); len=0;memset(last,0,sizeof(last)); for(int i=1;i<=m;i++) { int x,y;LL dd; scanf("%d%d%lld",&x,&y,&dd); ins(x,y,dd);ins(y,x,dd); } dis=0;getL(1,0,0); dis=0;getR(L,0,0); hp=1;p[hp]=L;h[hp]=0; memset(v,false,sizeof(v));v[L]=true; bk=false;dfs(L,0); return 0; }