2024蓝桥杯C++A组：团建（层序遍历）

题目描述

解题思路

先将树的孩子用vector容器进行存储，因题目说明每棵树不会有节点的值重复，故进行层序遍历，判断树的每层是否有相同结点值，以此判断最长公共前缀
 

附代码+注释

#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#define ll long long
using namespace std;
const int T = 200000;
vector<vector<int>> tree1(T);
vector<vector<int>> tree2(T);
vector<int> nums1(T);
vector<int> nums2(T);
int N, M;
int get() {
	int sum = 0;	
	int t1 = 1, t2 = 1;
	if (nums1[1] == nums2[1]) sum++;
	else return 0;
	while (1) {
		int i, j;
		int flag = 1;
		if (tree1[t1].size() == 0 || tree2[t2].size() == 0) break;
		for (i = 0; i < tree1[t1].size(); i++) {
			for (j = 0; j < tree2[t2].size(); j++) {
				if (nums1[tree1[t1][i]] == nums2[tree2[t2][j]])   //寻找公共前缀
				{
					flag = 0;
					t1 = tree1[t1][i];
					t2 = tree2[t2][j];                            //选取下一层的父节点
					sum++;
					break;
				}
			}
		}
		if (flag) break;
	}
	return sum;
}
int main() {
	cin >> N >> M;
	int n = N, m = M;
	int temp;
	while (n--) {
		cin >> temp;
		nums1[N - n] = temp;
	}
	while (m--) {
		cin >> temp;
		nums2[M - m] = temp;
	}
	n = N - 1; m = M - 1;
	int t1, t2;
	while (n--) {
		cin >> t1 >> t2;
		tree1[min(t1, t2)].push_back(max(t1, t2));
	}
	while (m--) {
		cin >> t1 >> t2;
		tree2[min(t1, t2)].push_back(max(t1, t2));       //存储每个节点的孩子
	}
	cout << get();
	return 0;
}