hdu 2196 Computer 树的直径

缘起

继续练习树的直径 hdu 2196 Computer 此题是树形dp超经典题~

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
对于树上（双向边）的每一个节点求出与其距离最远的点的距离。

【输入】
多样例. 每个样例首先是一个正整数N(N<=10000). 然后是N-1行，每一行

【输出】
对每个样例, 输出每个节点(因此有N行)到其他节点中最大的距离.

【样例输入】
5
1 1
2 1
3 1
1 1

【样例输出】
3
2
3
4
4

【限制】
1s

树形dp超经典题. 首先, 计算机之间形成的数据结构就是一棵（无向）树. 而计算一个顶点到其他所有顶点中最大的距离? 根据【1】中关于树的直径的论述，其实树上一个节点u到达树上的另一个节点P达到了最大的话, 则P一定是树的直径的一端. 而如果对每个顶点使用【1】中第一次bfs的手段. 则复杂度是O(N^2)的，对于N达到1w, 这种复杂度是不可接受的.

一定会被T掉! 但是真的有必要对每个树上的节点进行bfs么? 其实根据【1】中关于树的直径的论述，假设树的直径的另一端是Q. 即PQ是树的直径的话, 则树上任何一点达到它最大的距离一定要么是和P的距离要么是和Q的距离（此乃破题的关键！！！）（两者取大即可）. 所以这就好办了. 我们完全可以使用2次bfs，得到树的直径的两端. 并且在第二次bfs（即从P出发）的时候得到所有节点距离树的直径的一端的最长距离（其实哪有什么最长距离，树上任何两点之间的路径是唯一的.）, 然后再次从Q出发bfs得到其他节点到Q的距离. 然后两者取大即可.

当然，因为【1】中求树的直径使用了bfs, 这里换个花样——使用dfs求树的直径，都是搜索一样的复杂度~

好吧~ 我承认代码写的真丑~ 但是简明易懂~

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
//#define LOCAL

const int maxn = 10005;

struct Node
{
	int to, dis;
	Node(int to, int dis):to(to),dis(dis){}
};

int n,disp[maxn],disq[maxn], p,q, mmp,mmq; // p-q是树的直径, disp[i]是i到p的最远距离, disq[i]是i到q的最远距离
vector<Node> g[maxn];
typedef vector<Node>::iterator vit;

void dfsp(int cur, int fa) // cur是当前节点, fa是父节点, fa-cur是树边
{
	if (mmp<disp[cur])
	{
		mmp = disp[cur];
		p = cur;
	}
	for (vit x = g[cur].begin(); x!=g[cur].end(); x++)
	{
		if (x->to==fa)
		{
			continue;
		}
		disp[x->to] = disp[cur]+x->dis;
		dfsp(x->to, cur);
	}
}

void dfsq(int cur, int fa) // cur是当前节点, fa是父节点, fa-cur是树边
{
	if (mmp<disp[cur])
	{
		mmp = disp[cur];
		q = cur;
	}
	for (vit x = g[cur].begin(); x!=g[cur].end(); x++)
	{
		if (x->to==fa)
		{
			continue;
		}
		disp[x->to] = disp[cur]+x->dis;
		dfsq(x->to, cur);
	}
}

void dfs(int cur, int fa) // cur是当前节点, fa是父节点, fa-cur是树边
{
	for (vit x = g[cur].begin(); x!=g[cur].end(); x++) // 注意, q已经找到了, 不需要mmq啥的了~ 那玩意是找树的直径端点p、q要用的
	{
		if (x->to==fa)
		{
			continue;
		}
		disq[x->to] = disq[cur]+x->dis;
		dfs(x->to, cur);
	}
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d", &n))
	{
		for (int i = 1; i<=n; i++)
		{
			g[i].clear();
		}
		for (int i = 2,a,b; i<=n;i++)
		{
			scanf("%d%d", &a,&b);
			g[i].push_back(Node(a,b)),g[a].push_back(Node(i,b));
		}
		mmp = 0; // p记录了直径的一端, 而mmp记录了从任意一点(这里选1)出发和其他点之间的最远距离,最后被p达到,即mmp=1和p之间的距离
		memset(disp,0, sizeof(disp));
		dfsp(1,0);// 从任意一点（这里选取1）出发找树的节点的一端p
		mmp = 0;
		memset(disp, 0, sizeof(disp));
		dfsq(p,0); // 从p出发, 找树的直径的另一个端点q, 并且期间维护disp
		mmq = 0; // mmq记录了距离p的最远距离, 最后被q达到,即mmq=p和q之间的距离
		memset(disq, 0, sizeof(disq));
		dfs(q, 0); // 再从q出发dfs, 维护disq
		for (int i = 1; i<=n;i++)
		{
			printf("%d\n", max(disp[i], disq[i]));
		}
	}
	return 0;
}

ac情况

Status Accepted
Time 31ms
Memory 1932kB
Length 1791
Lang G++
Submitted 2019-09-10 09:39:47
Shared
RemoteRunId 30542550

参考

【1】https://yfsyfs.github.io/2019/09/10/poj-1985-Cow-Marathon-%E6%A0%91%E7%9A%84%E7%9B%B4%E5%BE%84/