HDU 4607 Park Visit 树的最大直径

题意：

　莱克尔和她的朋友到公园玩，公园很大也很漂亮。公园包含n个景点通过n-1条边相连。克莱尔太累了，所以不能去参观所有点景点。

经过深思熟虑，她决定只访问其中的k个景点。她拿出地图发现所有景点的入口都很特殊。所以她想选择一个入口，并找到一条最短的

路来参观k个景点。我们假设景点之间的距离为1。

解题思路：因为地图形状为树形，所以求树的最大直径。当k小于等于直径的时候输出k-1，当k大于直径的时候，因为访问了某一个景

需要返回直径所在的路径上，所以当k大于冷的时候结果为len-(k-len-1)*2。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

using namespace std;

const int maxn = 100005;

vector<int>tree[maxn];

int vis[maxn];

void init(int n){

    for( int i = 1; i <= n; i++)tree[i].clear();

}

int len;//保存树的最大直径

int dfs(int u){//求最大树的直径

    vis[u] = 1;

   int Max = 0,lMax = 0,i,j,size;

   size = tree[u].size();

   for( int i = 0; i < size; i ++){

        if( vis[tree[u][i]])continue;

        int tmp = dfs(tree[u][i]);

        if( tmp + 1  > Max){

            lMax = Max ;

            Max = tmp + 1;

        }else if( tmp + 1 > lMax)

            lMax = tmp + 1;

        if( len < Max + lMax)len = Max + lMax;

   }

   return Max;

}

int main(){

    int T,n,m;

    int u,v,k;

  // freopen("in.txt","r",stdin);

    scanf("%d",&T);

    while( T-- ){

        scanf("%d%d",&n,&m);

        init(n);

        for( int i = 1; i < n; i++){

            scanf("%d%d",&u,&v);

            tree[u].push_back(v);

            tree[v].push_back(u);

        }

        len = 0;

        memset(vis,0,sizeof(vis));

        dfs(1);

        // printf("%d\n",len);

        while( m-- ){

            scanf("%d",&k);

            if( k <= len)printf("%d\n",k-1);

            else printf("%d\n",len + (k-len-1)*2);

        }

    }

}

巴特西

HDU 4607 Park Visit 树的最大直径

最新文章

热门文章