Building Fire Stations Gym - 100554B

本文主要是介绍Building Fire Stations Gym - 100554B，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://codeforces.com/gym/100554/problem/B

考虑二分一个距离 看能否选两个点用这个距离把整个图覆盖 具体选哪两个点 肯定在直径上 感觉就在直径对称位置上 比赛时就想到这 然后居然觉得不对 还想了个例子把自己推翻了 真他妈智障啊。。其实正解就是这样

在直径对称位置上选择uv这两点后 整个树图被分为三块 uv子树各一块 剩下的为一块 u到直径端点就是我当前二分的这个距离 u子树上其余点到u肯定比这个距离要近啊 不然直径端点肯定不是当前这个了 当时就是没有想到这一点 还是对树的直径理解不够

 

#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5+10;struct node
{int v,next;
};queue <int> que;
node edge[2*maxn];
int first[maxn],fa[maxn],pre[maxn],book[maxn],dis[maxn];
int n,num,p1,p2,d;void addedge(int u,int v)
{edge[num].v=v;edge[num].next=first[u];first[u]=num++;
}void dfs(int cur,int &res,int &maxx,int dis)
{int i,v;if(maxx<dis) maxx=dis,res=cur;for(i=first[cur];i!=-1;i=edge[i].next){v=edge[i].v;if(v!=fa[cur]){fa[v]=cur;dfs(v,res,maxx,dis+1);}}
}void init()
{int u;fa[1]=0,d=0;dfs(1,p1,d,0);fa[p1]=0,d=0;dfs(p1,p2,d,0);num=0,u=p2;while(u!=0){pre[++num]=u;u=fa[u];}
}void bfs(int d,int u)
{int i,v;while(!que.empty()) que.pop();que.push(u);fa[u]=0,dis[u]=0,book[u]=1;while(!que.empty()){u=que.front();que.pop();if(dis[u]==d) continue;for(i=first[u];i!=-1;i=edge[i].next){v=edge[i].v;if(v!=fa[u]){fa[v]=u,dis[v]=dis[u]+1,book[v]=1;que.push(v);}}}
}bool judge(int d,int u,int v)
{int i;memset(book,0,sizeof(book));bfs(d,u),bfs(d,v);for(i=1;i<=n;i++) if(!book[i]) return 0;return 1;
}void solve()
{int i,l,r,m,ans,u,v;l=1,r=(num+1)/2;while(l<=r){m=(l+r)/2;if(judge(m-1,pre[m],pre[num-m+1])) r=m-1,ans=m-1,u=pre[m],v=pre[num-m+1];else l=m+1;}if(u==v) v=edge[first[u]].v;printf("%d %d %d\n",ans,u,v);
}int main()
{int t,i,u,v;scanf("%d",&t);while(t--){scanf("%d",&n);memset(first,-1,sizeof(first));num=0;for(i=1;i<=n-1;i++){scanf("%d%d",&u,&v);addedge(u,v),addedge(v,u);}init();solve();}return 0;
}/*
1
9
1 2
2 3
1 4
4 5
1 6
6 7
1 8
8 9
*/

 

这篇关于Building Fire Stations Gym - 100554B的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---