WikiwithEnergyFruits

NC219722. WikiwithEnergyFruits

描述

有一棵“魔法树”，它的神奇之处在于：“魔法树”的叶子节点可以结出一定数量的“能量果”，而“能量果”的数量等于该叶子节点所处的层数乘以其本身的编号，比如现有一棵如下结构的“魔法树”：

其中，编号 $“1”$ 为根节点，编号 $“2”$ 和编号 $“3”$ 为叶子节点，且两者都处于第 $2$ 层，所以编号 $“2”$ 的叶子节点能结出 $4$ 个“能量果”，编号 $“3”$ 的叶子节点能结出 $6$ 个“能量果”。

现在，给定一棵包含 $n$ 个节点的“魔法树”，为了计算方便，这里定义编号 $“1”$ 为根节点，请你计算一下，这棵“魔法树”一共能结出多少个“能量果”。

输入描述

第一行输入一个正整数，表示“魔法树”的节点个数
后面输入行，每行两个正整数和，其中表示为的父节点

输出描述

输出“魔法树”能结出的“能量果”总数

示例1

输入:

3
1 2
1 3

输出:

示例2

输入:

输出:

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

C(clang11) 解法, 执行用时: 22ms, 内存消耗: 1060K, 提交时间: 2021-03-21 19:11:15

#include<stdio.h>

int sign[100010];
int cnt[100010];
long long sum;

int main(){
	
	int n;
	int c, b;
	scanf("%d", &n);
	cnt[1] = 1;
	for( int i = 1; i < n; i++){
		scanf("%d %d", &b, &c);
		sign[b] = 1;
		cnt[c] = cnt[b] + 1;
	}
	for( int i = 1; i <= n; i++){
		if( sign[i] == 0){
			sum += i * cnt[i];
		}
	}
	printf("%lld", sum);
	return 0;
}

C++(clang++11) 解法, 执行用时: 56ms, 内存消耗: 1144K, 提交时间: 2021-03-23 09:35:46

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int s[2][100010];ll ans;
int main()
{
	int n;cin>>n;
	s[0][1]=1;
	for(int i=1;i<n;i++)
	{
		int a,b;cin>>a>>b;
		s[0][b]=s[0][a]+1;
		s[1][a]=1;
	}
	for(int i=2;i<=n;i++) if(!s[1][i]) ans+=(ll)s[0][i]*i;
	cout<<ans; 
}