首页 > 代码库 > hdu 4607 Park Visit 树的直径
hdu 4607 Park Visit 树的直径
对于一棵树,求遍历k个节点的最少步数。
先求出直径,若未超过直径,则就是k-1,否则就是 直径 + 2 * (k - 直径 - 1)。
#include <cstdio>#include <cstring>#include <algorithm>#include <queue>using namespace std;#define maxn 100100#define maxm 210000struct Node{ int u,v,next;}e[maxm];int head[maxn],cnt,w[maxn],s,maxlen;bool vis[maxn];void add(int u,int v){ e[cnt].u=u; e[cnt].v=v; e[cnt].next=head[u]; head[u]=cnt++; e[cnt].u=v; e[cnt].v=u; e[cnt].next=head[v]; head[v]=cnt++;}void bfs(int u){ queue <int> Q; memset(vis,0,sizeof(vis)); vis[u]=1; w[u]=0; s=u; Q.push(u); while(!Q.empty()) { int x=Q.front(); Q.pop(); for(int i=head[x];i!=-1;i=e[i].next) { int v=e[i].v; if(vis[v]) continue; vis[v]=1; w[v]=w[x]+1; Q.push(v); if(w[v]>maxlen) { s=v; maxlen=w[v]; } } }}int main(){ int cas,n,m,k; scanf("%d",&cas); while(cas--) { int i,u,v; scanf("%d%d",&n,&m); memset(head,-1,sizeof(head)); cnt=0; for(i=1;i<n;i++) { scanf("%d%d",&u,&v); add(u,v); } maxlen=-1; bfs(1); maxlen=-1; bfs(s); for(i=1;i<=m;i++) { scanf("%d",&k); if(k<=maxlen+1) printf("%d\n",k-1); else printf("%d\n",maxlen+2*(k-maxlen-1)); } } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。