L2-020 descendants of kung fu

题目链接

In the beginning, the simulation method was used,So it took a little more time,After reading other people's work, I know that it can be done with deep search.
If you use the simulation method, you need to pay attention：The apprentice's serial number may be higher than the master's serial number
For example, the bold part in the test case：

10 18.0 1.00
3 2 3 5
1 9
1 4
1 7
0 7
2 6 1
1 8
0 9
0 4
0 3

因此,For these points, it should be counted from the skill of the person behind,It needs to be pushed onto the stack first：The top of the stack is the last pushed,And its apprentice is under it,i.e. count after it.

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
const int MAX = 1e5 + 5;
struct Person {
    
	double power;	//power value
	vector<int> tudi;	//this man's apprentice
	int N;	//Get the multiplier of the disciple's skill
};
Person p[MAX];
stack<pair<int,int> > waiting;	//Apprentices who have not yet dealt with skills
double get_power(int x,double r) {
    		//Seek skill
	return (100 - r) * p[x].power / 100;
}
int main() {
    
	int N;
	double Z,r,ans=0;
	cin >> N >> Z >> r;
	p[0].power = Z;
	for (int i = 0; i < N ; i++) {
    
		int n,x;
		cin >> n;
		for (int j = 0; j < n; j++) {
    
			cin >> x;
			p[i].tudi.push_back(x);
			if (p[i].power > 0.001) {
    		//Master's power is known,Therefore, it can be regarded as an apprentice skill
				p[x].power= get_power(i, r);
			}
			else {
    	//Otherwise push on the stack
				waiting.push({
     i, x });
			}
		}
		if (n == 0) {
    
			cin>>p[i].N;
		}
	}
	//Handle unhandled apprentices
	while (!waiting.empty()) {
    
		pair<int, int> temp = waiting.top();
		waiting.pop();
		p[temp.second].power = get_power(temp.first, r);
	}
	//Seek the power of the Taoist
	for (int i = 0; i < N; i++) {
    
		if (p[i].N > 0) {
    		
			ans += p[i].power * p[i].N;
		}
	}
	cout << (int)ans;
	return 0;
}

The code is more concise by using deep search recursion！

#include<iostream>
#include<vector>
using namespace std;
const int MAX = 1e5 + 5;
vector<int> Map[MAX];
int N;
double Z, r, ans;
int other[MAX];
void DFS(int n,double power) {
    
	if (Map[n].size() == 0 && other[n] > 0) {
    
		ans += power * other[n];
		return;
	}
	for (int i = 0; i < Map[n].size(); i++) {
    
		DFS(Map[n][i], power * r);
	}
}
int main() {
    
	cin >> N >> Z >> r;
	int M;
	r = (100 - r) / 100;	//衰减值
	for (int i = 0; i < N; i++) {
    
		cin >> M;
		for (int j = 0; j < M; j++) {
    
			int x;
			cin >> x;
			Map[i].push_back(x);
		}
		if (M == 0)	cin >> other[i];
	}
	DFS(0, Z);
	cout << (int)ans;
	return 0;
}

方法2参考了这篇博客