题意：有$N$个点$M$条边的无向图。第$i$条边连接$a_i$和$b_i$，长度是$c_i$，流量是$f_i$。找一条$1$到$N$的路径使得最小流量和路径长度的比值最大。
题解：枚举那条边作为流量的最小值，只保留流量大于等于这条边的边。然后求出这条边分别到$1$和$N$的最短路即可。
题意：给出一棵$N$个点的树，每个点的权值$T_i$。有$M$个询问，每次询问$A_i$到$B_i$的路径上是否存在一个点权为$C_i$的点。
题解：可持久化线段树裸题
题意：有一个长度为$N$的字符串$S$，由前$M$个小写字母组成。字符$i$改成字符$j$的代价为$a_{i,j}$。你目的是使$S$可以分成若干段相同字符，每段长度不小于$K$。求最小代价。
题解：先对$a$搞一遍floyd求出字符$i$改成字符$j$的最小代价。令$dp_{i}$表示满足前缀$S[1..i]$的最小代价，那么考虑最后一段要变成$x$，那么$dp_{i}=\min\limits_{0 \le j \le i-k} {dp_{j} + sum_x(i)-sum_x(j)}$，其中$sum_x(i)$表示把前缀$S[1..i]$都变成$x$的最小代价。对于每个$x$维护$i-k$前面的$dp_j-sum_x(j)$的最值即可。
题意：有$N$个馅饼，依次标号为$1$到$N$。有$M$只奶牛，第$i$只重量为$w_i$，它会吃掉编号在区间$[l_i,r_i]$内的馅饼。你需要选出一个奶牛的序列$c_1,c_2,\dots,c_K$，使得这些奶牛依次吃馅饼的话，每头奶牛能至少吃掉一块馅饼。求出$w_{c_1}+w_{c_2}+\dots+w_{c_K}$的最大值。
题解：令$dp_{l,r}$表示吃掉的馅饼都在区间$[l,r]$内的最值。那么显然
其中$cost_{i,l,r}$是最大的$w_j$使得$l \le l_j \le i \le r_j \le r$。这里的意义是考虑$j$是最后一个吃的奶牛，并且它一定要吃掉馅饼$i$。
复杂度$O(N^3)$
题意：有一棵$N$个点的有根树，每个节点上有个set。有$Q$个操作：
-
$1\ x\ c$ ：把$c$加到以$x$为根的子树里每个节点的集合里 -
$2\ x$ ：求出以$x$为根的子树里每个点的集合大小之和
题解：考虑颜色$c$出现的位置，如果一个位置$x$有颜色$c$，它的一个祖先$y$也有颜色$c$，那么显然$x$可以不用考虑。于是对于每个颜色$c$我们有了一个位置集合$S_c$，其中两两不存在祖先关系。
对于一个询问操作，考虑颜色$c$的其中一个位置$u$，如果$x$是$u$的祖先，那么显然这个位置对答案的贡献是$size(u)$。如果$u$是$x$的祖先，那么显然这个位置对答案的贡献是$size(x)$。
于是对于一个询问$x$，我们只要分别算出这两种贡献即可。前者等价于子树求和，后者等价于到根的路径求和。这些在修改的时候也很容易维护。
题意：对于一个长度为$N$的排列$a={a_1,a_2,\dots,a_N}$，考虑如下函数生成它的BST：
generate(l,r): if l > r, return empty subtree; x = argmin_{l <= i <= r} a_i; // index of min a_i in {a_l,...,a_r} return a BST with x as the root, generate(l,x-1) as the left subtree, generate(x+1,r) as the right subtree;
对于所有逆序对个数为$K$的排列$a$，求出$\sum_a\sum_{i=1}^{N} d_i(a)$，其中$d_i(a)$是$a$中第$i$个节点的树高，对质数$M$取模。
题解：学了学题解的生成函数做法。根据构建BST个过程，可以发现
于是我们可以只关心满足且$a_j=\min(a_{j..i})$或者$a_j=\min(a_{i..j})$的$i$和$j$，不妨只考虑$i < j$。
考虑从$a_i$开始，挨个把数加进去，可以发现$a_{i..j-1}$的生成函数为
这时候加入$a_j$的话，又会增加$j-i$个逆序对，剩下$n-(j-i+1)$个数可以随便加，生成函数为
对应的贡献就是$x^{k-(j-i)}$的系数。
-
[Cave Paintings]
-
[Non-Decreasing Subsequences]
-
[Falling Portals]
题意：
题意：
题意：