HDU4607 - Park Visit(树的直径)

题目大意

给定一颗树，要求走过其中连续的k个点，使得步数最少

题解

每条边要么经过两次，要么一次，因为我们的目标就是使得走一次的边尽量的多，这样就转换成求树的直径了，求树的直径我用的是两次dfs,先随便从一个点开始dfs,找出以这个点为根距离它最远的结点，假设为s,然后再从s结点进行一个dfs,距离s结点最远的点与s点的距离就是树的直径(假设为d)，最后判断一下k和树的直径的大小，如果k-1小于树的直径，那么直接输出k-1,否则答案就是d+(k-1-d)*2

代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <vector>

using namespace std;

#define  MAXN 100005

vector<int>ivec[MAXN];

int ret,sum;

void dfs(int k,int fa,int dis)

{

    if(dis>sum)

    {

        sum=dis;

        ret=k;

    }

    int len=ivec[k].size();

    for(int i=0; i<len; i++)

        if(ivec[k][i]!=fa) dfs(ivec[k][i],k,dis+1);

}

int main()

{

    int T;

    scanf("%d",&T);

    while(T--)

    {

        int n,m;

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

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

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

        {

            int u,v;

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

            ivec[u].push_back(v);

            ivec[v].push_back(u);

        }

        ret=1;

        sum=0;

        dfs(ret,0,0);

        dfs(ret,0,0);

        while(m--)

        {

            int k;

            scanf("%d",&k);

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

            else

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

        }

    }

    return 0;

}