先将树的任意一条直径找出来,考虑树的直径一定是交于一条线段上的。
那么从直径两段往中间搜一定是中间这一段路径是唯一的。
设直径是$[s,t]$,把这个直径拉出来,左侧是$s$,右侧是$t$;
- 先以$s$为根,然后跑整一棵树,求出子树最长链和它的条数.
- 从$t$开始向左遍历整个直径,找到最左侧的一个点$v$使得其右侧相邻的一条边不是必经边(即使得当前点的右侧最长链条数不发生变化)
- 然后以$t$为根,然后跑整一棵树,求出子树最长链和它的条数.
- 从$s$开始向右遍历整个直径,找到最右侧的一个点$u$使得其左侧相邻的一条边不是必经边(即使得当前点的左侧最长链条数不发生变化)
- 链$[u,v]$中所有的边都是必经边。
上述过程显然是一个线性过程,复杂度是$O(n)$
```cpp
# include <cstdio>
# include <iostream>
# include <cstring>
# define int long long
using namespace std;
const int N=2e5+10;
struct rec{ int pre,to,w;}a[N<<1];
int n,tot;
int d[N],head[N],tim[N],f[N],path[N],pre[N];
void adde(int u,int v,int w)
{
a[++tot].pre=head[u];
a[tot].to=v;
a[tot].w=w;
head[u]=tot;
}
void dfs1(int u,int fa,int L)
{
d[u]=L;
for (int i=head[u];i;i=a[i].pre) {
int v=a[i].to; if (v==fa) continue;
dfs1(v,u,L+a[i].w);
}
}
void dfs2(int u,int fa,int L)
{
d[u]=L;
for (int i=head[u];i;i=a[i].pre) {
int v=a[i].to; if (v==fa) continue;
pre[v]=u; dfs2(v,u,L+a[i].w);
}
}
void dfs3(int u,int fa)
{
int cnt=0,mx=0; bool leaf=1;
for (int i=head[u];i;i=a[i].pre) {
int v=a[i].to; if (v==fa) continue; leaf=0;
dfs3(v,u);
if (f[v]+a[i].w>mx) mx=f[v]+a[i].w,cnt=tim[v];
else if (f[v]+a[i].w==mx) cnt+=tim[v];
}
if (leaf) f[u]=0,tim[u]=1;
else f[u]=mx,tim[u]=cnt;
}
signed main()
{
scanf("%lld",&n);
for (int i=1;i<n;i++) {
int u,v,w; scanf("%lld%lld%lld",&u,&v,&w);
adde(u,v,w); adde(v,u,w);
}
memset(d,0,sizeof(d));
dfs1(1,0,0); int s=0;
for (int i=1;i<=n;i++) if (d[i]>d[s]) s=i;
memset(d,0,sizeof(d));
dfs2(s,0,0); int t=0; pre[s]=-1;
for (int i=1;i<=n;i++) if (d[i]>d[t]) t=i;
printf("%lld\n",d[t]);
int u=t,v; while (pre[u]!=-1) path[++path[0]]=u,u=pre[u]; path[++path[0]]=u;
for (int i=1;i<=path[0]/2;i++) swap(path[i],path[path[0]-i+1]);
memset(f,0,sizeof(f)); memset(tim,0,sizeof(tim)); dfs3(s,0);
v=path[0];
for (int i=path[0]-1;i>=1;i--)
if (tim[path[i]]-tim[path[i+1]]>0) v=i;
memset(f,0,sizeof(f)); memset(tim,0,sizeof(tim)); dfs3(t,0);
u=1;
for (int i=2;i<=path[0];i++)
if (tim[path[i]]-tim[path[i-1]]>0) u=i;
printf("%lld\n",v-u);
return 0;
}
```