当前位置：网站首页>L2-020 功夫传人 (25 分)

L2-020 功夫传人 (25 分)

2022-04-23 00:33:00 【hys__handsome】

题目详情 - L2-020 功夫传人 (25 分) (pintia.cn)

注意审题，这里计算的是得道者功力总和。

思路：本质是一棵树，得道者都是叶子结点，所以直接dfs到叶子结点并计算总和即可。

#include<iostream>
#include<vector>
using namespace std;
const int N = 100010;
vector<vector<int>> g(N);
int a[N];
double sum = 0;

void dfs(int x,double gl,double r){
	if(g[x].empty()) sum += gl*a[x];
	for(int num:g[x]){
		dfs(num,gl*r,r);
	}
}

int main(){
    int n;
    double z,r;
    cin>>n>>z>>r;
    
    for(int i = 0; i < n; i++){
        int k; cin>>k;
        if(k == 0) cin>>a[i];
        for(int j = 0; j < k; j++){
            int x; cin>>x;
            g[i].push_back(x);
        }
    }
    
    dfs(0,z,(100-r)/100);
    cout<<(long long)sum;
    
    return 0;
}

版权声明
本文为[hys__handsome]所创，转载请带上原文链接，感谢
https://blog.csdn.net/hys__handsome/article/details/124343620

边栏推荐

猜你喜欢

随机推荐