题目描述
共两个问题，第一问求树的直径长度，第二问求直径的必须边
思路
第一问很好求，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
其实还有一种更为优美的做法。这里空间很大，我就写一下吧（
可以发现，直径的公共部分，一定是连在一起的。那么可以在第一问的时候求出直径长度，并把所有直径上的边权减一，然后再求一次直径，两次的差就是答案。
原因显然。