#include<bits/stdc++.h>
using namespace std;
#define edge(i,x) for(int i=h[x]; i; i=nt[i])
#define For(i,x,y) for(int i=x; i<=y; i++)
const int N=1e3;
int n,s,h[N],nt[N*2],to[N*2],w[N*2],cnt;
void add(int x,int y,int z)
{
nt[++cnt]=h[x]; h[x]=cnt; to[cnt]=y; w[cnt]=z;
}
int p[N],nxt[N];
int d[N],st,maxn,ed;
void dfs1(int x,int fa)
{
edge(i,x)
{
int y=to[i];
if(y==fa)continue;
//cout<<x<<" "<<y<<" ";
d[y]=d[x]+w[i];
// cout<<d[y]<<endl;
if(d[y]>maxn)
{
maxn=d[y],st=y;
}
dfs1(y,x);
}
}
int w1[N],w2[N];
void dfs2(int x,int fa)
{
edge(i,x)
{
int y=to[i];
if(y==fa)continue;
d[y]=d[x]+w[i];
if(d[y]>maxn)
{
maxn=d[y],ed=y;
}
p[y]=x;
dfs2(y,x);
}
}
void dfs3(int x,int fa)
{
d[x]=0;
edge(i,x)
{
int y=to[i];
if(y==fa||y==nxt[x]||y==p[x])continue;
dfs3(y,x);
d[x]=max(d[x],d[y]+w[i]);
}
}
int ans;
int main()
{
//freopen("text.in","r",stdin);
cin>>n>>s;
For(i,1,n-1){
int A,B,C;
cin>>A>>B>>C;
add(A,B,C);
add(B,A,C);
}
st=0,maxn=-1;
dfs1(1,0);
//cout<<maxn<<endl;
maxn=-1;
memset(d,0,sizeof(d));
dfs2(st,0);
//cout<<st<<" "<<ed<<endl;
int j=ed;
//for(int i=ed; i; i=p[i])
//{
// cout<<i<<" ";
//}
//cout<<endl;
for(int i=ed; i; i=p[i])
nxt[p[i]]=i;
ans=(1<<30);
//for(int i=ed; i; i=p[i])cout<<d[i]<<" ";
//cout<<endl;
for(int i=ed; i; i=p[i])
{
while(p[j]&&d[i]-d[p[j]]<=s)j=p[j];
ans=min(ans,max(d[ed]-d[i],d[j]));
}
//cout<<ans<<endl;
for(int i=ed; i; i=p[i])
dfs3(i,0),ans=max(ans,d[i]);//,printf("%d ",d[i]);
//cout<<endl;
cout<<ans<<endl;
}
标签:树网,NOIP2007,int,fa,edge,maxn,P1099
From: https://www.cnblogs.com/dadidididi/p/16800359.html