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;
}