#3057. 「HNOI2019」校园旅行

Summarize

给定一个有 $n$ 个节点、 $m$ 条边的简单无向图，每个节点有权值 $0$ 或 $1$。有 $q$ 次询问，每次询问两个节点 $u$、$v$ 间是否存在一条路径（可重复），使经过的节点权值为 $01$ 回文串。

$n \le 5000, m\le 500000, q\le 100000$

这里好像得写点什么…… oy 快帮我出出主意

行列式

定义：一个方阵的行列式表示为 $|A|$

$$
|A|=\sum_{p}(-1)^{\sigma(p)}\prod_{i=1}^na_i,p_i
$$

$$
\begin{aligned}
\left|\begin{array}{cccc}
a_{11} & a_{12} \
a_{21} & a_{22}
\end{array}\right| =a_{11}a_{22}-a_{12}a_{21}
\end{aligned}
$$

矩阵树定理

大雾

#3095. 「SNOI2019」字符串

Summarize

给出一个长度为 $n$的由小写字母组成的字符串 ，设其中第$i$ 个字符为 $a_i$。设删掉第 $i$个字符之后得到的字符串为$s _i$ ，请按照字典序对 $s_1$,…，$s_n$从小到大输出编号。若两个字符串相等，则认为编号小的字符串字典序更小。

$1 \le n \le 10^5$

感谢@oy的贡献

#3227. 「USACO 2019.12 Platinum」Bessie’s Snow Cow

Summarize

给定$n$个节点的一棵有根树，$q$次操作，每次操作可以令一个节点的子树的所有节点增加一个颜色$i$,或查询一个节点的颜色数

$1 \le n,q \le 10^5$

感谢@oy的贡献

#3226. 「USACO 2019.12 Platinum」Greedy Pie Eaters

Summarize

给定$n$个数中$m$个区间，每个区间有一个权值，要求输出总区间权值最大的一个序列使得每个序列不被之前的序列的并集完全覆盖

$1 \le n \le 300,1 \le m \le \frac{n(n-1)}{2}$

感谢@oy的贡献

这里好像得写点什么……