首页 > 代码库 > 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;}