蒟蒻第二次写题解，不清楚的地方见谅qwq

题目描述

共两个问题，第一问求树的直径长度，第二问求直径的必须边

思路

第一问很好求，lyd书里有，就不再赘述。
这里建议使用两次bfs的方法，因为关系到第二问的路径，这么做比较方便。
然后考虑第二问。
（注：必须边就是每条直径都要经过的一部分边）
容易知道，所有必须边构成一条链（有待证明）（其实是懒得想2333）
假设现在已经求得了一条直径的具体路径。设其两端分别为x和y。
从一端枚举到另外一端，并用l和r维护相交的部分。
先看x到y的。
设当前的节点为u。如果（u和x的距离）==（u不过直径能达到的最大长度），
说明u这里是直径的分叉口，l=u
再看y到x的。
同样的道理，若（u和y的距离）==（u不过直径的最大长度），r=u
这样就确定了l和r，完成！
（ps：记得开long long哦）

C++ 代码

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
int n,tot=0,head[N],rt1,rt2,q[N],h,t,fro[N],hh[N];
bool vis[N];ll dis[N];
struct edge
{
    int ver,nxt;
    ll w;
}e[N*2];

void mmax( ll &x,ll y )
{
    if ( y>x ) x=y;
}

void bfs( int st )
{
    memset( vis,0,sizeof(vis) );
    dis[st]=0; vis[st]=1; h=1; t=0; q[++t]=st;
    while ( h<=t )
    {
        int x=q[h++];
        for ( int i=head[x]; i; i=e[i].nxt )
        {
            int to=e[i].ver; 
            if ( vis[to] ) continue;
            dis[to]=dis[x]+e[i].w; vis[to]=1; fro[to]=x;
            q[++t]=to;
        }
    }
}

ll dfs( int x,int fa )
{
    if ( fa!=0 && vis[x] ) return 0;
    ll s=0;
    for ( int i=head[x]; i; i=e[i].nxt )
    {
        int to=e[i].ver;
        if ( to==fa || vis[to] ) continue;
        mmax( s,dfs( to,x )+e[i].w );
    }
    return s;
}

void add( int u,int v,ll w )
{
    tot++; e[tot].nxt=head[u]; e[tot].w=w; e[tot].ver=v; head[u]=tot;
}

int main()
{
    scanf( "%d",&n );
    for ( int i=1,x,y,l; i<n; i++ )
    {
        scanf( "%d%d%d",&x,&y,&l );
        add( x,y,l ); add( y,x,l );
    }

    ll s=0; int x,l,r;
    bfs( 1 );
    for ( int i=1; i<=n; i++ )
        if ( s<dis[i] ) s=dis[i],rt1=i;
    bfs( rt1 ); s=0; 
    for ( int i=1; i<=n; i++ )
        if ( s<dis[i] ) s=dis[i],rt2=i;
    memset( vis,0,sizeof(vis) );
    x=rt2; vis[rt1]=1;
    while ( x!=rt1 )
    {
        vis[x]=1; hh[fro[x]]=hh[x]+1; x=fro[x];
    }
    l=rt2; r=rt1; x=rt2; 
    while ( x!=rt1 )
    {
        s=dfs( x,0 );
        if ( s==dis[rt2]-dis[x] ) l=x; 
        if ( s==dis[x] )
        {
            r=x; break;
        }
        x=fro[x];
    }

    printf( "%lld\n%d",dis[rt2],hh[r]-hh[l] );
}

运行总时间：455ms 空间：15456 KB

完结撒花qwq

update

我找到证明了qwq
夏日大佬的一句话完结。
“显然直径的必须边一定连续，不然就成环了”
夏日大佬tql orz