【noip2007】树网的核

题解：

首先我们要知道一个性质：如果有多条直径 这个核不论在哪条直径上 答案都是一样的

这样我们就可以随便找一条直径 在这条直径上枚举核的位置

并且dfs预处理maxlon[i] (i在直径上) 表示到i的路径不经过直径的 离i最远的点到i的距离

这时核的偏心距就是max(maxlon[i],核的端点到直径的端点的长度) (i为核上的点)

这样就能O(n)求解

代码：

 #include <cstdio>

 const int N=,M=;

 struct inli{

     int next,data,lon;

     inli(const int a=,const int b=,const int c=):

         next(a),data(b),lon(c){}

 }line[N*];

 int S,n,m,son[N],fat[N],dis[N],bo[N],maxlon[N],seclon[N],hard[N],nl;

 int max(int x,int y){ return x>y ? x : y;}

 int min(int x,int y){ return x<y ? x : y;}

 void makedis(int t){

     bo[t]=;

     for (int i=son[t];i;i=line[i].next)

     if (!bo[line[i].data]){

         int ne=line[i].data;

         dis[ne]=dis[t]+line[i].lon;

         makedis(ne);

     }

 }

 void makefat(int t){

     for (int i=son[t];i;i=line[i].next)

     if (line[i].data!=fat[t]){

         int ne=line[i].data;

         fat[ne]=t;

         makefat(ne);

         if (maxlon[ne]+line[i].lon>maxlon[t]){

             seclon[t]=maxlon[t];

             maxlon[t]=maxlon[ne]+line[i].lon;

             hard[t]=i;

         }

     }

 }

 int makef(int x,int y){

     if (!x) return ;

     int i=hard[x];

     if (y<line[i].lon) return maxlon[x];

     return max(seclon[x],makef(line[i].data,y-line[i].lon));

 }

 int getans(){

     int res=;

     for (int i=S,x=seclon[S];i;x+=line[hard[i]].lon,i=line[hard[i]].data){

         if (x>res) break;

         res=min(res,max(makef(i,m),x));

     }

     return res;

 }

 int main(){

     scanf("%d%d",&n,&m);

     for (int x,y,z,i=;i<n;i++){

         scanf("%d%d%d",&x,&y,&z);

         line[++nl]=inli(son[x],y,z),son[x]=nl;

         line[++nl]=inli(son[y],x,z),son[y]=nl;

     }

     makedis();

     int x=;

     for (int i=;i<=n;i++)

     if (dis[i]>x) x=dis[i],S=i;

     makefat(S);

     printf("%d",getans());

 }