memset0 发布的文章

DP 。用 f_{u, 0} 表示 u 点被染黑的概率,f_{u, 1} 表示 u 点被染白,但是其祖先中有点被染黑的概率,用 f_{u, 2} 表示 u 点被染白,且其祖先没有被染黑的点的概率。所求答案即 \displaystyle{\sum_{i=1}^n f_{i, 0}}

READ MORE

考虑一段数 a_{l..r} 是公差为 k 的等差数列,当且仅当:

  • \max a_{l..r} - \min a_{l..r} = k(r - l)

  • \gcd abs(a_i - a_{i-1}) = k, (i \in (l, r])

  • \max pre_{l..r} < lpre_i 表示 a_i 上一次出现的位置。

线段树维护一下即可。

READ MORE

榕树还是当年的榕树,你却不是当年的你了……

先点名表扬下这个题面,写的也太优美了吧 QAQ ...

假设我们只需要判断 1 号点能否成为最后的答案,用 f_i 表示取完 i 所在的子树的所有点后榕树的心离 i 的最近距离,那么答案即求 [f_1 = 0].

考虑 f_u 怎么求,最难消去的孩子是 \max (siz_v) (v \in son_u) 的孩子 v ,可以用其他子树的 siz 来填补这棵子树。代码中,另一部分的大小表示为 half ,这一部分表示为 f[max]

对于不以 1 为根的情况,可以把根节点到当前点 u 的路径缩成一个点来考虑,可以上下 DP 。

READ MORE

一道傻逼 LCT ,结果调了好久。

首先直接离线处理,发现询问在中间做和在最后做是一样的,相当于一棵一棵树扫过去用 LCT 动态维护一个区间换父亲的操作,考虑用 LCT 建虚点,搞一搞即可。

需要注意这题查询两点间的距离的时候不能直接 split 出来,因为 LCT 上的 LCA 有可能是虚点,从而忽略了虚 LCA 到实 LCA 中间一段距离对答案的贡献。同时还注意点小细节,比如 1 号点的范围 233 .

另外这题保证了操作合法,就没必要费力不讨好的每次都 get_root 一下了,否则可能会 TLE 飞 。。。

关于如何求 LCT 上的 LCA :对于 \operatorname{access} 操作保存下最后一次的 \operatorname{splay}y 。先 \operatorname{makeroot}(root) ,再 \operatorname{access}(u) ,最后 \operatorname{access}(v) 返回的值就是答案。

READ MORE