树上计数
1¶
算是比较可做的树形 dp。除了最常规地预处理出只考虑 u 子树的序列数量，还需要去考虑只考虑除去（u 子树）再补上 u，并且让 u fix 在序列 \(j\) 位（所以每个点对应 \(O(n)\) 种状态）的序列数量。考虑往儿子这边走，这个过程会解锁掉儿子的兄弟对应的子树，但由于拓扑序的性质以及我们 dp 的顺序，新解锁的这些元素只能塞到已经确定好位置的 u 的后面，所以转移是可行的。想到这一步后面就是比较常规的优化。
2¶
对每个询问，把 每个与链相交的连通子图 挂到 链上位置最高（离根最近）的点 计数，恰好划分成三类： 一类挂在左链（不包含 lca）上；一类是挂在右链（不包含 lca）上；剩下的一类由于联通性，等价于会经过 lca。
对于前两类因为取的是位置最高的，所以不用再考虑子树之外的影响，所以也就是枚举左（右）链上的点，考虑这个点被子树中多少联通子图挂着，然后求和，可以树形 dp 处理； 最后一类就是数整棵树中包含它这个点的连通子图的数量，可以换根 dp 处理。
练习点： 换根的时候千万不要认为可以乘 0 的逆元，替代技术：（1）删掉点 i 的信息 = 前缀(i-1) 与 后缀(i+1) 合并；（2）维护乘积中有几个 0，也就是说得用一个二元组：(非零之积，零数量) 来充当 dp 对象。 没有修改的情况下，倍增法不仅可以求 lca，还可以求链上数据之和。主要是相对好写一点。