秦简

山河永寂，人间长情

0%

微软2017年预科生计划在线编程笔试 第2题 Tree Restoration

发表于 更新于 分类于

题目2 : Tree Restoration

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

There is a tree of N nodes which are numbered from 1 to N. Unfortunately, its edges are missing so we don’t know how the nodes are connected. Instead we know:

  1. Which nodes are leaves

  2. The distance (number of edges) between any pair of leaves

  3. The depth of every node (the root’s depth is 1)

  4. For the nodes on the same level, their order from left to right

Can you restore the tree’s edges with these information? Note if node u is on the left of node v, u’s parent should not be on the right of v’s parent.

tree-restoration.png

输入

The first line contains three integers N, M and K. N is the number of nodes. M is the depth of the tree. K is the number of leaves.

The second line contains M integers A1, A2, … AM. Ai represents the number of nodes of depth i.

Then M lines follow. The ith of the M lines contains Ai numbers which are the nodes of depth i from left to right.

The (M+3)-th line contains K numbers L1, L2, … LK, indicating the leaves.

Then a K × K matrix D follows. Dij represents the distance between Li and Lj.

1 ≤ N ≤ 100

输出

For every node from 1 to N output its parent. Output 0 for the root’s parent.

样例输入 

1
2
3
4
5
6
7
8
9
10
11
8 3 5  
1 3 4  
1  
2 3 4  
5 6 7 8  
3 5 6 7 8  
0 3 3 3 3  
3 0 2 4 4  
3 2 0 4 4  
3 4 4 0 2  
3 4 4 2 0

样例输出 

1
0 1 1 1 2 2 4 4

解析

根据已知条件复原树，似乎没有现成的算法可以套用。
那么我们来模拟我们的思维过程，将其流程化。
思路：
从底层出发，从左往右，依次判断。

  • 对于每层第一个节点，上一层的第一个非叶子节点必然是这个节点的父节点。
  • 此时记录该节点的父节点，并把父节点的子节点记录为当前节点，并以此更新这个父节点与其他已知节点的距离。
  • 然后看该层下一个节点。
    • 下一个节点若与前一个节点距离为2，则两者父节点相同。
    • 若大于2，则该节点的父节点是上一层的下一个非叶子节点。同时记录父、子节点，更新距离。
  • 如此每层循环，每层结束进入上一层，直到第二层。（第一层根节点不必再判断了。

AC代码（C++）：

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
103
104
105
#include<iostream>
using namespace std;

int main() {
	int N, M, K;
	//N is the number of nodes. M is the depth of the tree. K is the number of leaves.
	cin >> N >> M >> K;

	int depth[105] = { 0 };
	//depth[] represents the number of nodes of depth[i].
	for (int i = 0; i < M; i++) {
		cin >> depth[i];
	}

	int tree[105][105] = { 0 };
	//the nodes of depth[i] from left to right.
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < depth[i]; j++) {
			cin >> tree[i][j];
		}
	}

	int leaves[105] = { 0 };
	//leaves node
	int is_leaves[105] = { 0 };
	//Determine whether a node is a leaf node
	for (int i = 0; i < K; i++) {
		cin >> leaves[i];
		is_leaves[leaves[i]] = 1;
	}

	int dis[105][105] = { 0 };
	// the distance between Li and Lj.
	for (int i = 0; i < K; i++) {
		for (int j = 0; j < K; j++) {
			cin >> dis[leaves[i]][leaves[j]];
		}
	}

	int father[105] = { 0 };
	//answer
	int son[105] = { 0 };
	//record a child node of a node

	father[tree[0][0]] = 0;
	for (int i = 0; i < depth[1]; i++) {
		father[tree[1][i]] = tree[0][0];
	}

	for (int i = M - 1; i >= 2; i--) {
		int up_point = 0;
		////i-1层中第一个不是叶子节点的节点，必定是当前节点的父亲
		while (is_leaves[tree[i - 1][up_point]] && up_point < depth[i - 1]) {
			up_point++;
		}
		int point_a = tree[i][0];
		father[point_a] = tree[i - 1][up_point];
		son[tree[i - 1][up_point]] = point_a;
		//更新距离
		for (int k = 0; k < N; k++) {
			if (dis[point_a][k] > 0) {
				dis[father[point_a]][k] = dis[k][father[point_a]] = dis[point_a][k] - 1;
				}
		}

		for (int k = 0; k < K; k++) {
			dis[leaves[k]][father[point_a]] = dis[father[point_a]][leaves[k]] = dis[leaves[k]][point_a] - 1;
		}

		for (int j = 1; j < depth[i]; j++) {
			int point_b = tree[i][j];
			//如果和前一个节点u距离为2，说明父亲节点相同
			if (dis[point_a][point_b] == 2) {
				father[point_b] = father[point_a];
			}
			//否则，父亲节点是i-1层中下一个非叶子节点
			else {
				up_point++;
				while (is_leaves[tree[i - 1][up_point]] && up_point < depth[i - 1]) {
					up_point++;
				}
				father[point_b] = tree[i - 1][up_point];
				son[tree[i - 1][up_point]] = point_b;
				//更新距离
				for (int kk = 0; kk < N; kk++) {
					if (dis[point_b][kk] > 0) {
						dis[father[point_b]][kk] = dis[kk][father[point_b]] = dis[point_b][kk] - 1;
					}
				}
			}
			point_a = point_b;
		}
		//更新i-1层相邻节点的距离
		for (int kk = 0; kk < depth[i - 1] - 1; kk++) {
			if (!is_leaves[tree[i - 1][kk]] && !is_leaves[tree[i - 1][kk + 1]]) {
				dis[tree[i - 1][kk]][tree[i - 1][kk + 1]] = dis[tree[i - 1][kk + 1]][tree[i - 1][kk]] = dis[son[tree[i - 1][kk]]][son[tree[i - 1][kk + 1]]] - 2;
			}
		}
	}
	cout << father[1];
	for (int i = 2; i <= N; i++) {
		cout << " " << father[i];
	}
	return 0;
}

WA代码（C++）：

思路应该是没有问题的，但是结果WA，本地测试了几组数据没有问题。
可能的原因是部分边缘数据在算法中出了问题。
100个节点的数据太多了。暂时无法测试。

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
#include<iostream>
using namespace std;

int main() {
	int N, M, K;
	//N is the number of nodes. M is the depth of the tree. K is the number of leaves.
	cin >> N >> M >> K;

	int count_depth[105] = { 0 };
	for (int i = 1; i <= M; i++) {
		cin >> count_depth[i];
	}

	int tree[105][105] = { 0 };
	int depth_of_node[105] = { 0 };
	for (int i = 1; i <= M; i++) {
		for (int j = 1; j <= count_depth[i]; j++) {
			cin >> tree[i][j];
			depth_of_node[tree[i][j]] = i;
		}
	}

	int is_leaf[105] = { 0 };
	int num_leaf[105] = { 0 };
	for (int i = 1; i <= K; i++) {
		int TEMP;
		cin >> TEMP;
		num_leaf[i] = TEMP;
		is_leaf[TEMP] = 1;
	}

	int dis[105][105] = { 0 };
	for (int i = 1; i <= K; i++) {
		for (int j = 1; j <= K; j++) {
			cin >> dis[num_leaf[i]][num_leaf[j]];
		}
	}

	int father_node[105] = { 0 };
	
	int s_son_node[105] = { 0 };
	for (int i = 1; i <= N; i++) {
		if (is_leaf[i]) {
			s_son_node[i] = i;
		}
	}

	for (int i = M; i > 0; i--) {
		int count_top = 1;
		for (int j = 1; j <= count_depth[i]; j++) {
			if (j == 1) {
				for (; count_top <= count_depth[i - 1]; count_top++) {
					if (is_leaf[tree[i - 1][count_top]] != 1) {
						father_node[tree[i][j]] = tree[i - 1][count_top];
						s_son_node[tree[i - 1][count_top]] = tree[i][j];
						count_top++;
						break;
					}
				}
				continue;
			}
			if (dis[tree[i][j]][tree[i][j - 1]] == 2) {
				father_node[tree[i][j]] = father_node[tree[i][j - 1]];
			}
			else {
				for (; count_top <= count_depth[i - 1]; count_top++) {
					if (is_leaf[tree[i - 1][count_top]] != 1) {
						father_node[tree[i][j]] = tree[i - 1][count_top];
						s_son_node[tree[i - 1][count_top]] = tree[i][j];
						count_top++;
						break;
					}
				}
				continue;
			}
		}


		//更新上一层节点间距离
		for (int j = 1; j <= count_depth[i - 1]; )
		{
			for (int jj = j + 1; jj <= count_depth[i - 1]; jj++)
			{
				dis[tree[i - 1][j]][tree[i - 1][jj]] = dis[tree[i - 1][jj]][tree[i - 1][j]] = dis[s_son_node[tree[i - 1][j]]][s_son_node[tree[i - 1][jj]]] - (depth_of_node[s_son_node[tree[i - 1][j]]] - depth_of_node[tree[i - 1][j]]) - (depth_of_node[s_son_node[tree[i - 1][jj]]] - depth_of_node[tree[i - 1][jj]]);
			}
			j++;
		}
	}
	//输出
	for (int i = 1; i < N; i++)
	{
		cout << father_node[i] << " ";
	}
	cout << father_node[N];
	
	return 0;
}

最终结果

编号 题目 结果 语言 时间 内存
1490 Tree Restoration AC G++ 5ms 0MB