題目鏈接

首先找到樹的直徑，直徑左端點是a，直徑右端點是b，中間的點是mid（偶數的情況下mid可以看做兩個），兩點因該是左右分布；

假設兩點都不在直徑上，那么移到直徑上的話距離更短；

設直徑上左邊的消防站是x，右邊的消防站是y；

如果直徑上的兩個點不對稱的話，那個距離就肯定大于等于a到x，b到y；所以可以讓過度的點(已經滿足要求)一點，那樣更優而且并不影響；

直徑上的點更靠近中間的話，就更符合要求但是距離也會變大，就是單調的圖，由不行變成行；

現在就是要求行的分界線；

#include<cstdio> #include<iostream> #include<cstring> #include<vector> #include<queue> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; const int N=2e5+10,mod=1e6+3; int h[N],ne[N<<1],e[N<<1],idx=0;//鄰接表寸土 void add(int a,int b){ne[idx]=h[a],e[idx]=b,h[a]=idx++;return ;} int dis[N],dis1[N],dis2[N],n;//dist-直徑 dist1-左邊點 dist2-右邊點； vector<int>v;//存直徑 void dfs(int u,int fa,int dis[])//距離 {dis[u]=dis[fa]+1;for(int i=h[u];~i;i=ne[i]){int t=e[i];if(t==fa)continue;dfs(t,u,dis);}return ; } void zhijing()//找直徑上的點 {memset(dis,0,(n+5)*sizeof(int));dfs(1,0,dis);int ma=0;for(int i=2;i<=n;i++)if(dis[ma]<dis[i])ma=i;dfs(ma,0,dis);for(int i=1;i<=n;i++)if(dis[ma]<dis[i])ma=i;int sum=dis[ma];while(sum){for(int i=h[ma];~i;i=ne[i])if(dis[e[i]]==sum){ma=e[i];break;}v.push_back(ma);sum--;}return ; }int main() {int t;scanf("%d",&t);for(int _=1;_<=t;_++){scanf("%d",&n);idx=0;memset(h,-1,(n+5)*sizeof(int)); for(int i=1,l,r;i<n;i++)scanf("%d%d",&l,&r),add(l,r),add(r,l);v.clear();zhijing();int l=0,siz=v.size()-1,r=siz/2,ans=0;while(l<r){int mid=l+r>>1,ma=0;int a=v[mid],b=v[siz-mid];dfs(a,0,dis1);dfs(b,0,dis2);for(int i=1;i<=n;i++)ma=max(ma,min(dis1[i],dis2[i]));if(ma<=mid+1)r=mid;else l=mid+1;}dfs(v[l],0,dis1);dfs(v[siz-l],0,dis2);for(int i=1;i<=n;i++)ans=max(ans,min(dis1[i],dis2[i]));ans--;if(v.size()%2&&l==siz/2)r=siz;else r=siz-l;l=v[l],r=v[r];printf("%d %d %d",ans,l,r);if(_!=t)puts("");} return 0; } /* 1 13 1 2 2 3 3 4 3 5 5 7 5 6 5 9 9 8 9 10 10 11 10 12 7 13 一個樣例 */

總結

以上是生活随笔為你收集整理的Building Fire Stations的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。