沙堡-美团2023笔试(codefun2000)

题目链接
沙堡-美团2023笔试(codefun2000)

题目内容

塔子哥在海边建了一个沙堡乐园。里面有一个巨大的沙堡，塔子哥每年都会增加这个沙堡的层数，但也有一定的规律：
1、沙堡底层序号为 1 ；
2、沙堡的任何一个部分每年最多只能增加一个小沙堡(也可能不增加) ；
3、新建的小沙堡一定是独立的，没有和其他小沙堡连接(除了父亲沙堡)；
现在塔子哥准备了今年沙堡的示意图和明年沙堡的设计图，他想让你告诉他，第一座沙堡明年能否变成第二座沙堡。

输入描述

输出描述

如果第一座明年有可能建成第二座，输出“yes ”，否则输出”no”.

样例1

输入

1
5
1 1 1 4
8
1 1 1 4 5 1 4

输出

yes

样例1解释

样例2

输入

1
5
1 1 1 4
8
1 1 1 4 5 1 5

输出

no

样例2解释

题解1

#include<bits/stdc++.h>
using namespace std;

const int N = 5e4 + 10;

int t, n, m, cnt1[N], cnt2[N]; // cnt1[i]，cnt2[i]均表示以i为父节点的的总直系孩子节点个数 


int main(){
	scanf("%d", &t);
	while(t--){
		memset(cnt1, 0, sizeof cnt1);
		memset(cnt2, 0, sizeof cnt2);
		bool flag = true;
		scanf("%d", &n);
		for(int i = 2, u; i <= n; i++){
			scanf("%d", &u);
			cnt1[u]++;
			cnt2[u]=cnt1[u];
		}
		scanf("%d", &m);
		for(int i = 2, u; i <= n; i++){ // 由于两座沙堡的共有点的父节点相同，因此前(n-1)个沙堡相同 
			scanf("%d", &u);
		}
		
		for(int i = n + 1, u; i <= m; i++){
			scanf("%d", &u);
			cnt2[u]++;
			if(cnt2[u] - cnt1[u] > 1) flag = false; 
		}

		if(flag) printf("yes\n");
		else printf("no\n");
	}
	return 0;
}