D48 树的直径 P3304 [SDOI2013] 直径

// 树的直径 两次DFS+双指针 O(n)
#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int N=200005;
int n,p,r,l,pre[N],col[N];
ll mxd,cnt,d[N];
vector<pair<int,int>> e[N];

void dfs(int u,int fa){
  if(d[u]>d[p]) p=u; //记录直径端点
  pre[u]=fa;         //记录路径
  for(auto [v,w]:e[u])if(v!=fa&&!col[v]){
    d[v]=d[u]+w;
    dfs(v,u);
  }
}
int main(){
  ios::sync_with_stdio(0); cin.tie(0);
  cin>>n;
  for(int i=1,x,y,z;i<n;i++){
    cin>>x>>y>>z;
    e[x].emplace_back(y,z);
    e[y].emplace_back(x,z);
  }
  dfs(1,0); r=p; d[p]=0;
  dfs(p,0); l=p; mxd=d[p];
  for(int i=l;i;i=pre[i]) col[i]=1; //直径的点染色
  
  for(int i=l; i; i=pre[i]){ //双指针收缩路径
    ll ld=mxd-d[i], rd=d[i];
    p=i,d[p]=0;
    dfs(p,pre[p]); //搜索支路最长链
    if(d[p]==ld) l=i; //支路最长链=直径左段长度
    if(d[p]==rd){r=i;break;} //支路最长链=直径右段长度
  }
  for(int i=l;i!=r;i=pre[i]) cnt++;
  cout<<mxd<<"\n"<<cnt;
}

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
vector<pair<int,int>>G[N];
long long d[N],ans;int p;
void dfs1(int x,int fa)
{
    for(auto i:G[x])
    {
        int y=i.first,c=i.second;if(y==fa) continue;
        d[y]=d[x]+c;
        dfs1(y,x);
        if(ans<d[y]) ans=d[y],p=y;
    }
}
int D,f[N][20],dep[N],way[N],len;
void dfs2(int x,int fa)
{
    dep[x]=dep[fa]+1;
    f[x][0]=fa;for(int i=1;i<=D;i++) f[x][i]=f[f[x][i-1]][i-1];
    bool flag=0;
    for(auto i:G[x])
    {
        int y=i.first,c=i.second;if(y==fa) continue;
        flag=1;
        d[y]=d[x]+c;
        dfs2(y,x);
    }
    if(!flag) way[++len]=x;
}
int LCA(int x,int y)
{
    if(dep[x]<dep[y]) swap(x,y);
    for(int i=D;i>=0;i--)if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    if(x==y) return x;
    for(int i=D;i>=0;i--)if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    return f[x][0];
}
int main()
{
    int n;scanf("%d",&n);
    for(int i=1,x,y,c;i<n;i++)
	{
        scanf("%d%d%d",&x,&y,&c);
        G[x].push_back({y,c});G[y].push_back({x,c});
    }
    ans=0,memset(d,0,sizeof(d));dfs1(1,0);int L=p;
    ans=0,memset(d,0,sizeof(d));dfs1(L,0);int R=p;
    printf("%lld\n", ans);
    D=log2(n);memset(d,0,sizeof(d));dfs2(L,0);
    int t1=dep[R],t2=0;
    for(int i=1;i<=len;i++)
	{
        int x=way[i],y=R,lca=LCA(x,y);
        if(x==y) continue; 
        if(d[x]==d[y])      t1=min(t1,dep[lca]);//说明lca到lx的边为可能的必经边 
        if(d[x]==d[lca]*2)  t2=max(t2,dep[lca]);//说明lca到lx的边都不是必经边 
    }
    printf("%d\n",(t1-t2<0)?0:t1-t2);
    return 0;
}