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
************************************************ */
1#include <cstdio>
2#include <cstring>
3#include <iostream>
4#include <algorithm>
5#include <vector>
6#include <queue>
7#include <set>
8#include <map>
9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E5+7;
7vector< int >edge[N];
8int n,m;
9int d[N];
10int lst,beg;
11bool vis[N];
1void bfs( int s)
2{
3 ms(d,0);
4 ms(vis,false);
1 queue<int>q;
2 q.push(s);
3 vis[s] = true;
1 while(!q.empty())
2 {
3 int u = q.front();
4 q.pop();
5 // cout<<"u:"<<u<<endl;
6 int siz = edge[u].size();
7 for ( int i = 0 ; i <siz ; i++)
8 {
9 int v = edge[u][i];
10 if (vis[v]) continue;
11 d[v] = d[u] + 1;
12 vis[v] = true;
13 q.push(v);
14 }
15 }
16}
17int main()
18{
19#ifndef ONLINE_JUDGE
20 freopen("code/in.txt","r",stdin);
21#endif
22 int T;
23 cin>>T;
24 while (T--)
25 {
26 scanf("%d%d",&n,&m);
27 for ( int i = 1 ; i <= n ; i++) edge[i].clear();
28 for ( int i = 1 ; i <= n-1 ; i++)
29 {
30 int u,v;
31 scanf("%d%d",&u,&v);
32 edge[u].push_back(v);
33 edge[v].push_back(u);
34 }
1 bfs(1);
2 int mx = 0;
3 for ( int i = 1 ; i <= n ; i++)
4 {
5 if (d[i]>mx)
6 {
7 mx = d[i];
8 lst = i;
9 }
10 }
11 // cout<<endl;
12 bfs(lst);
13 mx = 0 ;
14 for ( int i = 1 ; i <= n ; i++)
15 {
16 if (d[i]>mx)
17 {
18 mx = d[i];
19 beg = i;
20 }
21 }
22 // cout<<"beg:"<<beg<<" lst:"<<lst<<endl;
23 // cout<<"mx:"<<mx<<endl;
24 while (m--)
25 {
26 int x;
27 int ans;
28 scanf("%d",&x);
29 if (x<=mx+1)
30 {
31 ans = x-1;
32 }
33 else
34 {
35 ans = mx + (x-mx-1)*2;
36 }
37 printf("%d\n",ans);
38 }
}
1#ifndef ONLINE_JUDGE
2 fclose(stdin);
3#endif
4 return 0;
5}