2023-09-23
题目
翻译
难度&重要性(1~10):6
题目来源
AtCoder
题目算法
模拟
解题思路
考场没调出来，考完赶紧写发题解祭奠一下。
这道题主要就是模拟，细节比较多。
思路就是一层一层的计算贡献：
如图，我们首先计算出以结点 \(x\) 为根的子树第 \(k\) 层的结点数，再计算结点 \(x\) 的父节点的另一个子节点的 \(k-1\) 层的结点数，以此类推，直到 \(k=1\)。
思路就是这样，但是有很多的小细节，例如：
-
在计算子树第 \(i\) 层的结点数时要判断是否存在这一层以及这一层是否是满的
-
当 \(k=1\) 时，需要判断当前是否时根节点，即当前 \(x\) 是否为 \(1\)，如果是则无贡献
完成状态
已完成