UVA10410 树重建 Tree Reconstruction

知识点：树的遍历

这个题考察的是对树的dfs和bfs遍历的理解，洛谷里面有一篇题解讲的特别清楚，我就是按照那种方法做的，

总的思路是用dfs序为基础，用bfs序为辅助来求，在dfs序上每个节点的父亲一定在这个节点的前面，那么我们就从dfs序上每个节点向前遍历找它的父亲，然后我们记录每个节点在bfs序列里面的位置，用来作为辅助，

假设当前节点是v，我们在dfs序里面从它向前遍历，找到第一个bfs序列位置小于v在bfs序列位置的节点，设为u，那么u只可能是v的左边的兄弟或者父亲，这是至关重要的一点，这个想明白了这个题就完成了一半，因为dfs序的特性，我们开始从v向前遍历的时候，一开始就是在v的父亲的子树里面遍历的，肯定不会超出这个范围，因为上面说了是第一个，在v的父亲的子树里面，一定有bfs序位置小于v的元素，可能直接就是父亲节点，如果v有左边的兄弟节点的话，那么就是兄弟节点，这就是我的理解的方式，洛谷的题解给了另外的理解方式

接下来，开始分类讨论判断，u在bfs序列里面的位置+1小于v在bfs序列里面的位置，也就是u和v在bfs序列里面不挨着，那么u一定是父亲，因为兄弟在bfs序列里面是一定挨着的

else，如果u大于v，那么u是父亲，因为题目说了节点的孩子是从小到大遍历的，如果是u小于v，那么u还是可能是兄弟或者父亲，具体的说分两种情况，1，如果没有深度和u相同且权值大于u的节点，和深度和v相同且父亲权值小于u的节点，这种情况，u是v的父亲或者兄弟都满足题意，都行，自己距离画图就知道，2，除了情况1，u只能是兄弟节点，所以逻辑很清晰了，任何时候，我们把这个bfs序位置+1等于v的bfs序位置的节点，当成是兄弟都不会出错的，只有情况1的时候，它即可能是兄弟也可能是父亲，但是那样显然是得不偿失的，因为我们要判断情况1就很困难，现有的条件应该是做不到的，就算是情况1判断出来了，那么u还是可能是兄弟或者父亲，还是可以选兄弟，所以不如一开始，在当前分支下面，一律认为u是兄弟，那么兄弟的父亲是相同的，v的父亲也就找到了

#include 
 
using namespace std;
 
const int N = 1005;
 
int main() {
	int n;
	while (cin >> n) {
		int a[N], b[N], bfs[N];
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
			bfs[a[i]] = i;
		}
		for (int i = 1; i <= n; i++) {
			cin >> b[i];
		}
		vector<int> v[N];
		int fa[N];
		v[b[1]].push_back(b[2]);
		fa[b[2]] = b[1];
		for (int i = 3; i <= n; i++) {
			int j = i - 1;
			while (j >= 1 && bfs[b[j]] > bfs[b[i]]) j--;
			if (bfs[b[j]] + 1 < bfs[b[i]]) {
				v[b[j]].push_back(b[i]);
				fa[b[i]] = b[j];
			} else {
				if (b[j] > b[i]) {
					v[b[j]].push_back(b[i]);
					fa[b[i]] = b[j];
				} else {
					v[fa[b[j]]].push_back(b[i]);
					fa[b[i]] = fa[b[j]];
				}
			}
		}
		for (int i = 1; i <= n; i++) {
			cout << i << ':';
			for (int j = 0; j < (int) v[i].size(); j++) {
				cout << ' ' << v[i][j];
			}
			cout << '\n';
		}
	}
	return 0;
}