P1099 树网的核——模拟+树形结构

P1099 树网的核

无根树，在直径上找到一条长度不超过s的路径，使得最远的点距离这条路径的距离最短；

首先两遍dfs找到直径（第二次找的时候一定要吧father[]清零）

在找到的直径下枚举长度不超过s的链，ans的下界是直径两端点到这条链距离的最小值；

然后将直径上的点都标记，再次求一下别的点到直径的距离。

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int maxn=;

 int n,s;

 int pre[maxn],last[maxn],other[maxn],len[maxn],l;

 void add(int x,int y,int z)

 {

     l++;

     pre[l]=last[x];

     last[x]=l;

     other[l]=y;

     len[l]=z;

 }

 int dis[maxn],father[maxn],vis[maxn];

 int l1,l2;

 void dfs(int x)

 {

     for(int p=last[x];p;p=pre[p])

     {

         int v=other[p];

         if(v==father[x]||vis[v]) continue;

         father[v]=x;

         dis[v]=dis[x]+len[p];

         dfs(v);

     }

 }

 int main()

 {

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

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

     {

         int x,y,z;

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

         add(x,y,z);

         add(y,x,z);

     }

     dis[]=; dfs();

     l1=;

     for(int i=;i<=n;i++) if(dis[i]>dis[l1]) l1=i;

     memset(father,,sizeof(father));

     dis[l1]=; dfs(l1); l2=;

     for(int i=;i<=n;i++) if(dis[i]>dis[l2]) l2=i;

     //printf("??%d %d\n",l1,l2);

     int ans=,j=l2;

     for(int i=l2;i;i=father[i])

     {

         while(father[j]&&dis[i]-dis[father[j]]<=s) j=father[j];

         ans=min(ans,max(dis[l2]-dis[i],dis[j]));

     }

     for(int i=l2;i;i=father[i]) vis[i]=;

     for(int i=l2;i;i=father[i])

     {

         dis[i]=;

         dfs(i);

     }

     for(int i=;i<=n;i++) ans=max(ans,dis[i]);

     printf("%d",ans);

     return ;

 }