L2-020 功夫传人

### 关于PAT L2-020 功夫传人的解题思路 此问题是关于树结构的遍历以及计算节点属性的一个典型应用。题目要求通过给定的数据构建一棵师徒关系树，并基于特定规则计算所有得道者的功力总值。 #### 数据处理与建模 输入数据提供了每个人的徒弟列表，因此可以将其视为一个图中的邻接表表示法。由于每个人都只有一个师父（除了祖师爷），这实际上是一个单向无环图（即树）。可以通过广度优先搜索 (BFS)[^2] 或深度优先搜索 (DFS)[^3] 来遍历该树。 #### 计算逻辑 1. **初始条件** 祖师爷的功力值 \( Z \) 是已知的，每一代弟子的功力会按照一定比例减少，具体由参数 \( r \% \) 控制。对于任意一个人 \( i \)，其功力值可定义为： \[ P_i = P_{\text{master}} \times (\frac{r}{100})^{d} \] 其中 \( d \) 表示当前节点距离根节点的距离（代数）[^1]。 2. **特殊规则** 如果某个人被标记为“得道者”，则他们的功力会被放大一定的倍数。注意，这种放大的效果仅适用于他们本身，而不会传递给后代。最终的结果应直接取整而非四舍五入[^4]。 3. **算法选择** 可以采用 BFS 遍历来逐层访问每一个节点并更新相应的功力值。或者使用 DFS 进行递归求解，在回溯过程中累加符合条件的功力值[^5]。 #### 示例代码实现 以下是 Python 的一种可能实现方式： ```python import sys from collections import deque def main(): input_data = sys.stdin.read().splitlines() line_1 = list(map(float, input_data[0].split())) N, Z, R = int(line_1[0]), line_1[1], line_1[2]/100 children = [[] for _ in range(N)] ascended = [False]*N multipliers = [1.0]*N for idx in range(1, N+1): info = list(input_data[idx].split()) if info[0] != '0': child_list = list(map(int,info[1:])) children[idx-1] = child_list if len(info) >= 2 and info[-1][0]=='@': # Check last element is '@X' multiplier = float(info[-1][1:]) ascended[idx-1] = True multipliers[idx-1] = multiplier queue = deque([(0,Z)]) total_power = 0 while queue: current_node,power = queue.popleft() if ascended[current_node]: power *= multipliers[current_node] total_power += int(power) next_gen_power = power * R for child in children[current_node]: queue.append((child,next_gen_power)) print(total_power) if __name__ == "__main__": main() ``` 上述代码实现了利用队列完成层次遍历的过程，并依据是否为得道者调整了对应的功力值计算方法。 ###