hdu 4607 Park Visit

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树DP

【2013多校联合训练第一场】

题意:给出一棵无根树,边的距离都是1。对于查询m,意思是你要去到m个点,但是走过的距离最短,这里是允许走回头路,即一条路可以走多次,每走一次算1次距离

要距离最短,可以想到,不要走回头路就最好了。它又没规定起点和终点只是说走m个点,那就很宽松了。我们可以在树中找到最长链,这里定义最长链用点来定义,1->2->3,认为长度是3,经过的边是2,maxlink = 3

如果整个树的最长链 maxlink > m , 那么就可以在最长链上走,这样一定不会走完,也就不需要走回头路。走了m个点,走过的边就是m-1,所以距离就是m-1

如果对于整课树的最长链都少于m,那么就无可避免要揍回头路。首先我们从最长链的头走到尾,那么就走了maxlink个点,走了maxlink-1条边,还剩下m-maxlink个点要走,那么只好往回走,走到某点x,从这点出去走向另一个方向,再走m-maxlink个点就完成任务。但是可以从一个点x出去,走到底都走不够m-maxlink个点,那么又得走回头路,这个问题看起来就很复杂了,但是其实想想就知道,因为深度的关系,每次走下去又走回头路,都是走掉的距离的2倍。一开始走了maxlink个点,剩下m-maxlink个点,其实无论最后怎么走,回头路和新走出来的路都是m-maxlink(往深度那里想想或者画画图就出来了),答案为maxlink - 1 + 2*(m-maxlink)

找最长链用树DP,对于每个点记录最远距离和次元距离,注意这里的距离一定在不同分支,比较简单的树dp,算是本场比赛第2水的题了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 100010
#define cl memset
#define pb push_back

int n,q,dp[N][2],id[N][2],maxlink; //不需要id数组,只是为了debug查看而已
vector<int>e[N];
bool vis[N];


void dfs(int u){
vis[u] = true;
dp[u][0] = dp[u][1] = 0;
id[u][0] = id[u][1] = -1;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
if(vis[v]) continue;
dfs(v);
if(dp[v][0] > dp[u][0]){
dp[u][1] = dp[u][0]; id[u][1] = id[u][0];
dp[u][0] = dp[v][0]; id[u][0] = v;
}
else if(dp[v][0] > dp[u][1]){
dp[u][1] = dp[v][0]; id[u][1] = v;
}
}
dp[u][0]++; dp[u][1]++;
maxlink = max(maxlink , dp[u][0] + dp[u][1] - 1);
}

int main(){
int cas;
scanf("%d",&cas);
while(cas--){
for(int i = 0; i <= n; i++){
e[i].clear();
vis[i] = false;
}
scanf("%d%d",&n,&q);
for(int i = 1; i < n; i++){
int u,v;
scanf("%d%d",&u,&v);
e[u].pb(v); e[v].pb(u);
}
maxlink = -1;
dfs(1);

// printf("maxlink = %d\n",maxlink);
// for(int i = 1; i <= n; i++){
// printf("%d : %d[%d] %d[%d]\n",i,dp[i][0],id[i][0],dp[i][1],id[i][1]);
// }

while(q--){
int m;
scanf("%d",&m);
if(m <= maxlink)
printf("%d\n",m-1);
else
printf("%d\n",maxlink-1+(m-maxlink)*2);
}

}
return 0;
}