题目大意

有一棵$n$个节点的树，点有点权，对于每个节点，你要求出离这个节点距离$k$以内的节点的点权和

$1 \leq n \leq 10^5, 1 \leq k \leq 20$

题目大意

有一个有$n$个点的有向完全图，每条边每天有一个开放几率$p[i][j]$，给定$p$，你需要求出从$1$到$n$的期望天数

$n \leq 10^3$

题目大意

有一个长度为$n$的序列${a_i}$，每次可以选择连续的$3$个数，把中间那个数加到左右两个数上后删除中间那个数。

求最后剩下的两个数的最小值。 $n \leq 18$

题目大意

你有一个长度为$n$的串$\texttt{S}$，其中有一些位置上的字符是?，其他的字符则是$0/1$之间的一种

每次可以进行一步操作：选择$3$个连续的字符，并把它们用它们的中位数替换

求有多少种把?替换成$0/1$的方案使得在进行$\frac{n-1}{2}$次操作后剩下的字符为$1$？

题目大意

有一棵有$n$个节点的树，每个节点上有$0/1$枚棋子，每次可以选择两个棋子并移动到它们的路径上的相邻节点（满足路径长度至少为$2$），求把所有棋子移到同一个节点的最小花费（无解输出$-1$）。

$n \leq 2 \times 10 ^ 3$

斜率优化的练手题

通读题目可以发现
$$
f_i=\max (f_j+g(s[i]-s[j]))
$$

$$
其中f_i表示在i处强制结束一段的最大代价,s_i表示a_i的前缀和,g(x)表示(ax^2+bx+c)
$$

题目大意

给你$n$个点,$m$条边,要你选一个点作为根建一棵生成树满足代价最小

一棵生成树的代价是$\Sigma \; dep[i] * dis[fa_i][i]$, 其中$dep_i$表示$i$节点在这棵生成树中的深度（根节点深度为$0$,$dis[fa_i][i]$表示$i$节点到他父亲节点的距离

设$f_u$表示$u$不被以$u$为根的子树内点(包括$u$)通上电的概率，则有:

$$f_u=(1-p_u) \times \prod_{v \in subtree \; u}e(u, v) \times f_v$$

一道简单的动态规划