MAO! GIVE ME LOVE 君
gimmick gimmick LOVE
どうか笑ってダーリン
MAO! GIVE ME LOVE 君
gimmick gimmick LOVE
今夜最後まで 鳴らせ
——洛天依《MAO!》
AT_arc121_e
思维难度：\(\color{#FFC116} 黄\) *1500
这也能反演 /jy
要求的条件是排列 \(a\) 满足每个 \(a_i\) 都不是 \(i\) 的祖先。
但是这个东西不好数。
注意到「都不是」，也就是说恰好 \(0\) 个不是，所以可以反演。发现钦定 \(i\) 个不合法是好数的，于是直接子集反演做完了。
注意此处不是二项式反演，因为数出来的东西即使都是钦定 \(i\) 个不合法，但钦定不同的点所形成的结构是不一定相同的。所以钦定 \(i\) 个不合法就等价于所有大小为 \(i\) 的子集。
还有一点转化：因为直接按照祖先数的话，子树之间会产生冲突，所以需要把 \(a_i\) 是 \(i\) 的祖先转化为 \(i\) 在子树 \(a_i\) 内（不包含 \(a_i\)），因为 \(i\) 和 \(a_i\) 都是 \(1 \sim n\) 的排列所以两者是双射的。
被这个转化硬控一上午最后找 gpt 才解决了.jpg
哦具体数的方法就是树上背包，这个是容易的。
submission
天依宝宝可爱！