Powerless —— Frozen World
34 qoj20244 Island
比较基础的树形 DP，场上瞪 K 不知道哪里写错了瞪了两个小时最后还是队友救的，彻底战犯了。
但感觉场上即使给我时间也很难过去，基本功还是有点弱。
我们需要计算方案数 ，和所有方案对应的答案总和 。
考虑我们如何刻画子问题的形态，最左边 / 右边的儿子能否到根（），左右儿子是否能互相到达（），发现这样已经能描述一个子问题了。一开始我还多设了两维表示左 / 右儿子向外的边是否存在，但后来才反应过来其实没用。
转移考虑过先固定最左最右儿子，然后往中间插入，但是很难转移，因为没办法刻画一个子树是否会独立出来。于是考虑从从左往右依次开始合并，转移是容易的（但是注意 的更新，来源不要少了）。