D48 树的直径 P3304 [SDOI2013] 直径

视频链接：

P3304 [SDOI2013] 直径 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

// 两次 DFS O(n)
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long ll;
const int N=200005;
struct edge{
  int to,w,ne;
}e[N<<1];
int head[N],idx;
void add(int x,int y,int w){
  e[++idx]={y,w,head[x]};
  head[x]=idx;
}
int n,p,l,r,pre[N],col[N];
ll d[N],mxd;

void dfs(int x,int fa){
  pre[x]=fa;
  for(int i=head[x];i;i=e[i].ne){
    int y=e[i].to,w=e[i].w;
    if(y==fa) continue;
    d[y]=d[x]+w;
    if(d[y]>mxd) mxd=d[y],p=y;
    dfs(y,x);
  }
}
void dfs2(int x,int fa){
  for(int i=head[x];i;i=e[i].ne){
    int y=e[i].to,w=e[i].w;
    if(col[y]||y==fa) continue;
    d[y]=d[x]+w;
    if(d[y]>mxd) mxd=d[y];
    dfs2(y,x);
  }
}
int main(){
  scanf("%d",&n);
  for(int i=1,x,y,z;i<n;i++){
    scanf("%d%d%d",&x,&y,&z);
    add(x,y,z); add(y,x,z);
  }
  dfs(1,0);
  d[p]=mxd=0; l=p; //记录直径左端点
  dfs(p,0);
  r=p; //记录直径右端点
  printf("%lld\n",mxd);
  
  for(int i=r;i;i=pre[i])col[i]=1; //标记直径
  int ll=l,rr=r;
  for(int i=pre[rr];i!=ll;i=pre[i]){
    int ld=d[i],rd=d[rr]-d[i];
    d[i]=mxd=0;
    dfs2(i,0);
    if(mxd==rd) r=i;
    if(mxd==ld){l=i;break;}
  } //区间[l,r]为公共路径
  if(l==r) puts("0");
  else{
    int cnt=1;
    for(int i=pre[r];i!=l;i=pre[i]) cnt++;
    printf("%d\n",cnt);
  }
}