Day1

T1

打出 \(n^2\) dp，找到规律，直接计算。

可以用导数证明公式

T2

咕

T3

愚蠢的在线法官

我会 \(n^3\)！

\(A_{a,b}=f_{lca(a,b)}\rightarrow A_{a,b}=w_x[a|x][b|x]\)

\(w_x\) 可以树上差分由 \(f_x\) 得到。

一个点对矩阵的 \(i\in[l,r],j\in[l,r]\) （\(l,r\) 是子树 dfn 序）有矩阵加，矩阵上二维差分不影响行列式，所以变成了四个单点加，发现是矩阵树的形式。

转化为求 \(l,r+1\) 间连边的生成树数量，用广义串并联图求生成树的方法求生成树得到矩阵的行列式。

匹配计数

对每一个颜色赋一个权值，要求 \(3\) 变成了要求有偶数个逆序对，于是对每对逆序对连边，要求导出子图的边数为偶数。

要求 \(2\) 则利用“偶减奇”的套路，对每种颜色额外连一个源点，若颜色数为偶数则会贡献翻倍，否则贡献为 \(0\)。

把边写成邻接矩阵的形式，用 bitset 进行消元计算边数偶数的导出子图，复杂度 \(O(\frac{n^3}{w})\)。