对于一棵树，求遍历k个节点的最少步数。
先求出直径，若未超过直径，则就是k-1，否则就是 直径 + 2 * (k - 直径 - 1)。
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; #define maxn 100100 #define maxm 210000 struct 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 ",k-1); else printf("%d ",maxlen+2*(k-maxlen-1)); } } return 0; }