Note: This article is available in Chinese only. 本文暂无英文版本。
View original
hdu4607题目链接 题意：给出一棵树。。。边权都为1. m个查询。。每个查询给一个k，表示只访问k个点。。。问每次的最小路径和是多少。。。 思路：我们发现。。会使路径和变大的一个不利因素是折返。。也就是访问某景点后。。必须要回去才能继续前进。。这样的距离是2倍。。那为了使得路径和尽可能小。。我们就尽量不要访问这样的点。。。而不是这样的点一定在直径上。。。以及我们还发现。。。不在直径上的点。。 。。不管深度如何（深度的意思是说，与和该点最近的直径上的点的距离），距离的贡献是一样的。。都是2倍。。所以我们可以推出一个公式。。。如果树的直径是d，那么k<=d+1的时候，答案为k-1，否则答案为d+(k-d-1)*2。。。
因为bfs的时候忘记标记起点WA了一发蠢哭。。。。2A
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年07月13日 星期三 14时33分29秒
4File Name :code/poj/4607.cpp
5 ************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E5+7;
34vector< int >edge[N];
35int n,m;
36int d[N];
37int lst,beg;
38bool vis[N];
39
40void bfs( int s)
41{
42 ms(d,0);
43 ms(vis,false);
44
45 queue<int>q;
46 q.push(s);
47 vis[s] = true;
48
49 while(!q.empty())
50 {
51 int u = q.front();
52 q.pop();
53 // cout<<"u:"<<u<<endl;
54 int siz = edge[u].size();
55 for ( int i = 0 ; i <siz ; i++)
56 {
57 int v = edge[u][i];
58 if (vis[v]) continue;
59 d[v] = d[u] + 1;
60 vis[v] = true;
61 q.push(v);
62 }
63 }
64}
65int main()
66{
67#ifndef ONLINE_JUDGE
68 freopen("code/in.txt","r",stdin);
69#endif
70 int T;
71 cin>>T;
72 while (T--)
73 {
74 scanf("%d%d",&n,&m);
75 for ( int i = 1 ; i <= n ; i++) edge[i].clear();
76 for ( int i = 1 ; i <= n-1 ; i++)
77 {
78 int u,v;
79 scanf("%d%d",&u,&v);
80 edge[u].push_back(v);
81 edge[v].push_back(u);
82 }
83
84 bfs(1);
85 int mx = 0;
86 for ( int i = 1 ; i <= n ; i++)
87 {
88 if (d[i]>mx)
89 {
90 mx = d[i];
91 lst = i;
92 }
93 }
94 // cout<<endl;
95 bfs(lst);
96 mx = 0 ;
97 for ( int i = 1 ; i <= n ; i++)
98 {
99 if (d[i]>mx)
100 {
101 mx = d[i];
102 beg = i;
103 }
104 }
105 // cout<<"beg:"<<beg<<" lst:"<<lst<<endl;
106 // cout<<"mx:"<<mx<<endl;
107 while (m--)
108 {
109 int x;
110 int ans;
111 scanf("%d",&x);
112 if (x<=mx+1)
113 {
114 ans = x-1;
115 }
116 else
117 {
118 ans = mx + (x-mx-1)*2;
119 }
120 printf("%d\n",ans);
121 }
122
123 }
124
125#ifndef ONLINE_JUDGE
126 fclose(stdin);
127#endif
128 return 0;
129}