题解

#include <bits/stdc++.h>
using namespace std;

const int maxn=310;
int n,m,size,len,ans=1e9,maxx;
int f[maxn][maxn],dis[maxn],first[maxn],vis[maxn],v[maxn],tag[maxn];
struct shu{int to,next,len;}edge[maxn<<1];
int get_int()
{
	int x=0;char c;
	for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
	return x;
}

void build(int x,int y,int z)
{
	edge[++size].next=first[x],first[x]=size,edge[size].to=y,edge[size].len=z;
	edge[++size].next=first[y],first[y]=size,edge[size].to=x,edge[size].len=z;
}

void init()
{
	n=get_int(),m=get_int();
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<n;i++)
	{
	  int x=get_int(),y=get_int(),z=get_int();
	  build(x,y,z),f[x][y]=f[y][x]=z;
	}
}
void pre()
{
	for(int k=1;k<=n;k++)
	  for(int i=1;i<=n;i++)
	    for(int j=1;j<=n;j++)
	      f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
	for(int i=1;i<=n;i++)
	{
	  f[i][i]=0;
	  for(int j=1;j<=n;j++) if(i!=j) len=max(len,f[i][j]);
	}
	for(int i=1;i<=n;i++)
	  for(int j=1;j<=n;j++)
	    if(i!=j&&f[i][j]==len)
	    {
	      vis[i]=vis[j]=1;
	      for(int k=1;k<=n;k++)
	        if(j!=k&&i!=k&&f[i][k]+f[k][j]==len) vis[k]=1;
	    }
}
void dfs(int p,int d)
{
	tag[p]=1;
	maxx=max(maxx,d);
	for(int u=first[p];u;u=edge[u].next)
	{
	  int to=edge[u].to;
	  if(tag[to]||v[to]) continue;
	  tag[to]=1;
	  dfs(to,d+edge[u].len);
	}
}
void solve()
{
	for(int s=1;s<=n;s++)
	  for(int t=1;t<=n;t++)
	  if(vis[s]&&vis[t]&&f[s][t]<=m)
	  {
	  	maxx=0;
	 	memset(v,0,sizeof(v)),memset(tag,0,sizeof(tag));
	  	for(int k=1;k<=n;k++) if(f[s][k]+f[k][t]==f[s][t]&&vis[k]) v[k]=1;
	  	for(int k=1;k<=n;k++) if(v[k]) dfs(k,0);
	  	ans=min(ans,maxx);
	  }
	cout<<ans;
}

int main()
{
	init();
	pre();
	solve();
	return 0;
}

直接暴力dfs，时间复杂度O(n^3)