为什么深进和置顶题解,在我注释的一行(即求直径的第一次dfs)前,都加了 dis[1]=1 啊?感觉好像没什么区别,请问有什么意义吗?
#include<bits/stdc++.h>
#define N 303
using namespace std;
int n,s,ans=2e9,far;
int dis[N],fa[N];
bool flag[N];
int head[N],cnt;
struct star{
int next,to,val;
}e[N<<1];
void add(int u,int v,int w){
e[++cnt].next=head[u];
e[cnt].to=v;
e[cnt].val=w;
head[u]=cnt;
}
void dfs(int u,int f){
fa[u]=f;
if(dis[u]>dis[far]) far=u;
for(int i=head[u];i;i=e[i].next){
int v=e[i].to,w=e[i].val;
if(v==f||flag[v]) continue;
dis[v]=dis[u]+w,dfs(v,u);
}
}
signed main(){
cin.tie(0),cout.tie(0);
ios::sync_with_stdio(0);
cin>>n>>s;
for(int i=1,u,v,w;i<n;i++)
cin>>u>>v>>w,add(u,v,w),add(v,u,w);
int a,b;
//dfs(1,0),a=far;
dis[a]=0,dfs(a,0),b=far;
for(int i=b,j=b;i;i=fa[i]){
while(dis[j]-dis[i]>s) j=fa[j];
ans=min(ans,max(dis[b]-dis[j],dis[i]));
}
for(int i=b;i;i=fa[i]) flag[i]=1;
for(int i=b;i;i=fa[i])
dis[i]=0,dfs(i,fa[i]);
for(int i=1;i<=n;i++)
ans=max(ans,dis[i]);
cout<<ans;
return 0;
}
(应该不难理解这些变量的意思吧)