hdu 4607 Park Visit (树的直径，推公式)

hdu4607题目链接 题意：给出一棵树。。。边权都为1. m个查询。。每个查询给一个k,表示只访问k个点。。。问每次的最小路径和是多少。。。 思路：我们发现。。会使路径和变大的一个不利因素是折返。。也就是访问某景点后。。必须要回去才能继续前进。。这样的距离是2倍。。那为了使得路径和尽可能小。。我们就尽量不要访问这样的点。。。而不是这样的点一定在直径上。。。以及我们还发现。。。不在直径上的点。。 。。不管深度如何（深度的意思是说，与和该点最近的直径上的点的距离），距离的贡献是一样的。。都是2倍。。所以我们可以推出一个公式。。。如果树的直径是d,那么k<=d+1的时候，答案为k-1,否则答案为d+(k-d-1)*2。。。

因为bfs的时候忘记标记起点WA了一发蠢哭。。。。2A

/* ***********************************************
Author :111qqz
Created Time :2016年07月13日 星期三 14时33分29秒
File Name :code/poj/4607.cpp
 ************************************************ */

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
vector< int >edge[N];
int n,m;
int d[N];
int lst,beg;
bool vis[N];

void bfs( int s)
{
    ms(d,0);
    ms(vis,false);

    queue<int>q;
    q.push(s);
    vis[s] = true;

    while(!q.empty())
    {
	int u = q.front();
	q.pop();
	//	cout<<"u:"<<u<<endl;
	int siz = edge[u].size();
	for ( int i = 0 ; i <siz ; i++)
	{
	    int v = edge[u][i];
	    if (vis[v]) continue;
	    d[v] = d[u] + 1;
	    vis[v] = true;
	    q.push(v);
	}
    }
}
int main()
{
#ifndef  ONLINE_JUDGE 
    freopen("code/in.txt","r",stdin);
#endif
    int T;
    cin>>T;
    while (T--)
    {
	scanf("%d%d",&n,&m);
	for ( int i = 1 ; i <= n ; i++) edge[i].clear();
	for ( int i = 1 ; i <= n-1 ; i++)
	{
	    int u,v;
	    scanf("%d%d",&u,&v);
	    edge[u].push_back(v);
	    edge[v].push_back(u);
	}

	bfs(1);
	int mx = 0;
	for ( int i = 1 ; i <= n ; i++)
	{
	    if (d[i]>mx)
	    {
		mx = d[i];
		lst = i;
	    }
	}
	//	    cout<<endl;
	bfs(lst);
	mx = 0 ;
	for ( int i = 1 ; i <= n ; i++)
	{
	    if (d[i]>mx)
	    {
		mx = d[i];
		beg = i;
	    }
	}
	//	    cout<<"beg:"<<beg<<" lst:"<<lst<<endl;
	//	    cout<<"mx:"<<mx<<endl; 
	while (m--)
	{
	    int x;
	    int ans;
	    scanf("%d",&x);
	    if (x<=mx+1)
	    {
		ans = x-1;
	    }
	    else
	    {
		ans = mx + (x-mx-1)*2;
	    }
	    printf("%d\n",ans);
	}

    }

#ifndef ONLINE_JUDGE  
    fclose(stdin);
#endif
    return 0;
}