种树

NC213758. 种树

描述

scimoon 种了一棵以1为根的有根树，树上的节点要么有两个儿子，要么是叶子节点，节点 i 有一个生命力 $val_i$

scimoon 心血来潮，决定修建枝桠

每次 scimoon 会选择一个树杈 u 进行修剪，要求这个节点有两个儿子，并且这两个儿子均为叶子节点

修建之后，u 的两个儿子都会被剪掉，而 u 变成了一个叶子节点

若用大园林剪，则会使 $val_u=\max(val_{ls_u},val_{rs_u})$

若用小园林剪，则会使 $val_u=\min(val_{ls_u},val_{rs_u})$

其中 $ls_u$ 表示 u 的左儿子， $rs_u$ 表示 u 的右儿子

scimoon 剪得上头，一不小心剪得只剩下了根节点，scimoon 预测到会发生这样的事，于是给根节点留下了最大的生命力

scimoon 力气不够，若共修建 m 次，则最多只能用 $\lfloor\frac{m+1}{2}\rfloor$ 次大园林剪

聪明的你一定能算出根节点最后的生命力是多少

输入描述

第一行一个整数 n

接下来 n 行，每行两个正整数，表示  和 ，若为 0 则表示没有该儿子

接下来一行 n 个整数 ，表示初始权值，不保证只有叶节点有权

输出描述

一个整数，根节点最后的生命力

示例1

输入:

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C 解法, 执行用时: 31ms, 内存消耗: 1912K, 提交时间: 2021-06-14 14:21:39

#include<stdio.h>
int a[500005]={0};
int b[500005],l[500005],r[500005];
int max;
void bfs(int i,int k){
	if(l[i]==0){
		if(k<=max)
		a[i]=1;return ;
	}
	bfs(l[i],k+1);bfs(r[i],k+1);
	return ;
}
int main()
{
	int i,j,k,n,m,max1=-1;
	scanf("%d",&n);m=n;
	for(i=1;i<=m;i++)scanf("%d%d",&l[i],&r[i]);
	n/=2;
	if(n%2==1)max=n/2+1;
	else
	max=n/2;bfs(1,0);
	for(i=1;i<=m;i++){
	scanf("%d",&b[i]);}
	
	for(i=1;i<=m;i++)if(a[i]==1&&b[i]>max1)max1=b[i];
	printf("%d",max1);
}

C++ 解法, 执行用时: 66ms, 内存消耗: 1756K, 提交时间: 2022-04-13 19:06:59

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;
const int N=100010;

int l[N],r[N],a[N],ans,n,m;

void dfs(int u,int d)
{
	if(!l[u])
	{
		if(d<=m)ans=max(ans,a[u]);
		return ;
	}
	dfs(l[u],d+1),dfs(r[u],d+1);
}

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>l[i]>>r[i];
	for(int i=1;i<=n;i++)cin>>a[i];
	m=(n/2+1)/2;
	dfs(1,0);
	cout<<ans<<endl;
}