Lct

介绍

实质上是维护森林, 支持了许多动态操作:

  • 查询, 修改链上的信息(最值, 总和等)
  • 动态添删边
  • 动态维护连通性等功能

而它依靠的是虚实边的动态维护!

继续阅读 Lct

[Pkuwc2018] Minimax

sol

  • 说在前头

考虑直接维护每个叶子作为当前子树的根的概率.

设当前叶子u作为子树根的值的概率为f(u)

发现a, b 2个子树合并时, 子树a的某一叶子u为根的概率:

f'(u) = \sum_{v\in \text{subtree}_b} [V_v < V_u] p_x\cdot f(v)f(u) +\sum_{v\in \text{subtree}_b} [V_v > V_u] (1-p_x)\cdot f(v)f(u)

继续阅读 [Pkuwc2018] Minimax

[Cf53E] Dead Ends

sol

考虑如何将恰好k个叶子变成求至少k个叶子.

我们可以强行枚举叶子, 即求

  • 至少包含S集合的点为叶子的方案数.

    这个可以将非S的集合做一遍\text{matrix-tree}定理

那么接下来就可以子集卷积了

继续阅读 [Cf53E] Dead Ends

[Zjoi2019] 麻将

麻将真好(du)van(liu)

  • 首先考虑对于一个状态来说: 摆牌的顺序是没有关系的, 只与牌数有关.

那么如何确定当前局面能否胡牌?

  1. 7个对子胡牌的情况非常好判断.
  2. 考虑顺子胡牌的情况:

继续阅读 [Zjoi2019] 麻将