塔子哥的完整二叉树-小米2023笔试(codefun2000)

题目链接
塔子哥的完整二叉树-小米2023笔试(codefun2000)

题目内容

塔子哥有一棵节点数为 n 的完整二叉树，对于一个完整二叉树的定义是：要么每个节点有两个子节点，要么每个节点没有子节点。

• 没有子节点的节点，其权值为 1 。
• 有两个子节点的节点，其权值为两个儿子节点的权值的运算结果。

每个节点有两种运算，要么为加法，要么为乘法。如下给出一个长度为 n 的数组 c 。
ci =0 表示节点 i 的运算是加法，ci=1 表示节点 i 的运算是乘法。
现在，塔子哥问你这个完整二叉树的根节点的权值是多少。

输入描述

第一行，一个正整数 n($1\le n\le 10^5$) 表示完整二叉树中的节点个数。
第二行，n−1 个正整数 p[2,3,…,n]，pi 表示第 i 个节点的父节点，1 号节点是根节点。
第三行，n 个整数 c[1,2,…,n] ，含义如题面描述所示
数据保证形成满足题目描述的二叉完整树。

输出描述

一个整数，表示根节点的值，答案对 $10^9+7$ 取模。

样例1

输入

3
1 1
1 1 1

输出

1

样例1解释

2 号节点和 3 号节点权值均为 1 ，1 号节点是乘法运算，故 1 号节点的权值为 1 。

题解1

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 1e5 + 10; const LL MOD = 1e9 + 7;  int n, p[N], c[N]; vector<int> edge[N]; bool vis[N];  LL dfs(int u){ 	vis[u] = 1; 	int sz = int(edge[u].size()); 	if(!sz) return 1; 	LL left = dfs(edge[u][0]); 	LL right = dfs(edge[u][1]); 	if(!c[u]) return (left + right)%MOD; 	else return (left * right)%MOD;  } int main(){ 	scanf("%d", &n); 	for(int i = 2; i <= n; i++){ 		scanf("%d", &p[i]); 		edge[p[i]].emplace_back(i); 	} 	for(int i = 1; i <= n; i++) scanf("%d", &c[i]); 	printf("%lld\n", dfs(1)); 	return 0; }