P4719 【模板】"动态 DP"&动态树分治 P4719 【模板】”动态 DP”&动态树分治 先不考虑修改，可以想到 $\tt Dp$： 设 $f(i, 0/1)$ 表示当前的点是否选择，那么转移可以得到：$$\begin{aligned}f(u, 0) &= \sum_{v \in son_u} \max(f(v, 0), f(v, 1))\f(u, 1) &= \sum_{v \in son_u} f(v, 0)\end{aligned}$$发现每一次进行修改的时候影响的是一条链上的信息，我们不妨将其树链剖分一下，设 $g(u, 0/1)$ 表示亲儿子对应的信息。$$\begin{aligned}g(u, 0) =& \sum_{v \in sonlight_u} \max(f(v, 0), f(v, 1)) \g(u, 1) =& \sum_{v \in sonlight_u} f(v, 0)\end{aligned}$$我们可以把转移变成矩阵：$$\left[\begin ...

CF1197E Culture Code CF1197E Culture Code 显然 $\tt Dp$ 肯定是不能依赖于体积的。我们考虑选择当前位置的方案。 容易发现每个点能选择的对象构成了一个 $\tt DAG$。 设 $f(i)$ 表示选择了点 $i$ 的最小剩余体积，显然 $f(i) = -in(i) + \min_{j} f(j) + out(j)$，后面的东西直接使用前缀维护即可。 对于方案数我们可以同样维护一个前缀和，但是其代表的是考虑了点 $i$ 得到最终答案是 $f(i)$ 的最小方案。 设 $g(i)$ 表示最终最小值是 $f(i)$ 的时候，考虑了 $1 \sim i$ 的答案。 显然这个东西包含了之前的所有合法方案。 因为如果当前点是终止点，之后不会让其贡献重复叠加。 如果当前点不是终止点，那么其贡献还可能更新到之后的点改变。 但是我们需要保证 $out$ 的合法性，直接按照 $out$ 排序，之后二分得到即可。 本题比较难处理的就是 $\tt Dp$ 的边界，但是知道这个是拓扑图了之后肯定就没有问题了。 起始点，显然其 $in < ...

P5298 [PKUWC2018]Minimax $2021.10.8$ 重新自己写出这题。 其实不要想太复杂就好了，别忘了看题面。 先给一个提示吧，为什么这题的 $Dp$ 不用融斥掉中间的部分，题目已经说出来了：没有重复权值的叶子。 首先考虑对于每一个节点的值最多只有 n 个，所以肯定需要离散化。之后考虑实际上每一个节点的值都是从其子树的叶子节点中转移过来的。 所以考虑树形 Dp 设 $f[i][j]$ 表示在树上点 $i$ 其值为 $j$ 的概率。 当然是离散化之后的值。 我们考虑转移，根据题意是取 $\min, \max$ 来转移的，所以我们考虑左右两个儿子的大小关系。具体来说就是如果让左边的儿子产生了贡献，右边的儿子的值就一定比左边儿子小 ( 如果是取 $\min$ 的话 )。 就可以写出方程 这里设左边的儿子为 l 右边的儿子为 r $$\begin{aligned}f[i][j] &= f[l][j] \times (p_i \times \sum_{k = 1} ^ {j - 1} f[r][k] + (1 - p_i) \t ...

P3412 仓鼠找sugar II P3412 仓鼠找sugar II 根据期望的线性性质我们考虑对于每一条边进行计算贡献。 我们可以考虑先算方案数再除以总的点对。 根据期望的定义本质上就是平均数，那么对于一条边 $u \to v$ 的贡献次数就是 $(n - siz(u)) \times siz(u)$。 我们考虑一条边有两种情况： 向上 向下 我们钦定点 $u$ 表示 $fa(u) \to u$ 的边。 设 $up(u)$ 表示这条边从下走到上 $u \to fa(u)$。 设 $dn(u)$ 表示这条边从下走到上 $fa(u) \to u$。 $up(u)$ 一共有两种情况： $u \to v \to u \to fa(u)$ $u \to fa(u)$。 $$\begin{aligned}up( u) &= \frac{1}{deg(u)} + \sum_{v \in son(u)} \frac{up(v) + up(u) + 1}{deg(u)}\&= deg(u) + \sum_{v \in son(u)} up(v)\ ...

[HNOI2013]游走 [HNOI2013]游走 考虑每一条边的单独贡献，发现这个不是很好计算，而且边数其实很多。 我们考虑对于一条 $u \to v$ 的边，其贡献是 $\dfrac{f(u)}{deg(u)} + \dfrac{f(v)}{deg(v)}$。 其中 $f(i)$ 表示点 $i$ 期望被经过的次数，别忘了一开始点 $1$ 就被经过一次了。 考虑走到别的点之后再走回来更新这个点：$$f(u) = \sum_{v \in son(u)} \frac{f(v)}{deg(v)}$$如果 $u = 1$ 还要 $+ 1$。 发现数据范围很小，我们直接进行高斯消元即可。 之后对于边的期望经过次数进行贪心即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091 ...

[HNOI2015]亚瑟王 [HNOI2015]亚瑟王 根据期望的线性性质，我们考虑每一张牌的贡献。也就是每一张牌被使用的概率。 显然第一张牌使用的概率就是 $1 - (1 - p_1) ^ r$。 但是发现之后的牌的使用依赖于前面的牌的使用，因为如果前面有 $j$ 张牌被使用了，相当于有 $j$ 轮对于当前牌是无效的。 我们考虑进行 $\tt dp$，设 $f(i, j)$ 表示前 $i$ 张使用了 $j$ 张牌的概率。$$f(i, j) =\begin{cases}f(i - 1, j) \times \left(1 - p_i\right)^{r - j} \f(i -1, j - 1) \times \left[1 - (1 - p_i)^{r - j + 1}\right]\end{cases}$$ $$F(i) =\begin{aligned}\sum_{k \le i} f(i - 1,k) \times \left[1 - (1 - p_i)^{r -j}\right]\end{aligned}$$ 1234567891011121314151 ...

[六省联考2017]分手是祝愿 [六省联考2017]分手是祝愿 对于每一种情况，我们肯定是从大到小依次进行操作，那么对于一次操作是不能用其他操作进行代替的。 如果可以代替要么代替的那个变得不合法，要么其本身就是不用进行操作的。 所以我们可以直接计算出来原来序列需要进行多少次方案。 根据期望的线性性，而且现在本质上只和操作正确的次数有关，我们直接对于有几个还要操作进行 $\tt Dp$。 设 $f(i)$ 表示从还有 $i$ 个需要进行操作到 $i - 1$ 个需要的期望步数。$$f(i) = \frac{i}{n} + \frac{n - i}{n} \times (f(i + 1) + 1) \f(n) = 1$$然后题目的限制得到 $f(i) = 1, i \le K$。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727 ...

全局平衡二叉树 P4751 【模板】"动态DP" P4751 【模板】”动态DP”&动态树分治（加强版） 有事没事就用 $\tt vector$ 总会有天废掉的。 注意在 $\tt c++11$ 之后 $\tt vector$ 不管是是否在 $O2$ 的条件下，速度都比常规数组慢很多，甚至比链表要慢 $4$ 倍。 死亡写法： 123456789struct Tree : vector<vector<int>> { Tree() : vector<vector<int>>(2, vector<int>(2, -inf)) {} Tree operator * (const Tree &z) { Tree res; for(int i = 0; i < 2; ++ i) for(int j = 0; j < 2; ++ j) for(int k = 0; k < 2; ++ k) ...