天梯赛L2-020 功夫传人(dfs)

思路:使用set存需要计算的徒弟，map记录增加的倍数,然后dfs跑一遍即可

include [HTML_REMOVED]

using namespace std;

const int N = 1e5 + 10;
typedef long long ll;
vector[HTML_REMOVED] p[N]; // 树的邻接表
double sum = 0, z, r;
int n;
unordered_set[HTML_REMOVED] leaf_nodes; // 存储叶子节点的索引
unordered_map[HTML_REMOVED] leaf_values; // 叶子节点的权值

void dfs(int u, int dep)
{
if (leaf_nodes.count(u)) // 叶子节点
{
sum += (z * pow(1.0 - r / 100, dep)) * leaf_values[u];
return;
}

for (auto v : p[u])
{
    dfs(v, dep + 1);
}

}

int main()
{
cin >> n >> z >> r;
for (int i = 0; i < n; i)
{
int x;
cin >> x;
if (x != 0)
{
for (int j = 0; j < x; j) // 这里修正为 x 个子节点
{
int z;
cin >> z;
p[i].push_back(z);
}
}
else
{
int b;
cin >> b;
leaf_nodes.insert(i); // 存储索引，而不是值
leaf_values[i] = b; // 存储对应的叶子节点的值
}
}

dfs(0, 0);
cout << (int)sum;
return 0;

}