zcmimi's blog

arrow_back共17篇文章

avatar
zcmimi
2019-01-20 00:22:39
avatar
zcmimi
2018-12-29 22:31:53

学习的原因:

之所以选择fhqtreap,不是因为可以可持久化,是因为:

1. 短

2. 好理解、好记

3. 应用范围广

不过学之前还是先对treap原理稍微有些了解比较好

其中有些细节还是要靠自己意会意会

原理:

概述:

f

avatar
zc
2020-09-29 12:40:52

查看原题

点击跳转

s_i为每个连通块点数

对每个连通块构建prufer序列

由于度数为边数两倍,\displaystyle \sum_{i=1}^k d_i=2k-2

对于给定d序列构造prufer序列的方案数为:

\displaystyle {k-2\choose d_1-1,d_2-1,\dots,d_k-1} = \frac{(k-2)!}{(d_1-1)!(d_2-1)!\cdot(d_k-1)!}

对于第i个连通块,它的连接方式有s_i^{d_i}种,对于给定d序列使图连通的方案数为:

\displaystyle {k-2\choose d_1-1,d_2-1,\dots,d_k-1}\cdot \prod_{i=1}^k s_i^{d_i}

枚举d序列:

\displaystyle \sum_{d_i\ge 1,\sum d_i=2k-2} {k-2\choose d_1-1,d_2-1,\dots,d_k-1}\cdot \prod_{i=1}^k s_i^{d_i}

换元,设e_i=d_i-1:

\displaystyle \sum_{e_i\ge 0,\sum e_i=k-2} {k-2\choose e_1,e_2,\dots,e_k}\cdot \prod_{i=1}^k s_i^{e_i+1}

根据多元二项式定理:

\displaystyle (x_1+x_2+\dots+x_m)^p=\sum_{c_i\ge 0,\sum c_i=p} {p\choose c_1,c_2,\dots,c_m}\cdot \prod_{i=1}^m x_i^{c_i}

原式化简得:

\displaystyle (s_1+s_2+\dots+s_k)^{k-2}\cdot \prod_{i=1}^k s_i

\displaystyle n^{k-2} \cdot \prod_{i=1}^k s_i

avatar
zc
2020-09-08 20:15:00
查看原题

点击跳转

首先两次dfs找出任意一条直径

设直径为序列A,L_i为点i到直径左端的距离,R_i为点ii到直径右端的距离

可以发现这条直径把树分割成了若干棵子树,直径上每个点对应一颗子树

mxd_ii点对应子树的最大深度

从左到右枚举,直到mxd_i<L_i,得到l

从右到左枚举,直到mxd_i<R_i,得到r

序列Alr之间的点都是必须经过的点

avatar
zc
2020-05-03 11:51:00
查看原题

点击跳转

交互题

我们从叶子节点开始搜索,把所有叶子节点添加到队列中

每次从队列中弹出两个叶子节点,

如果lca为其中一个,那么这个lca就是树根

否则删除这两个节点,可能会形成新的叶子节点,加入队列

因为最坏情况下每次都会删掉两个节点,那么重复\frac n2次后,也就只剩下根节点了

avatar
zc
2020-05-03 11:09:00
查看原题

点击跳转

可以发现有三种路径:

  1. a \leftrightarrow b

  2. a \leftrightarrow x \leftrightarrow y \leftrightarrow b

  3. a \leftrightarrow y \leftrightarrow x \leftrightarrow b

只需要判断这三条路径是否满足就可以了

可以发现只要dis\le k而且和k同奇偶就是符合的

(比如x\leftrightarrow y可以一直循环,变成x\leftrightarrow y \leftrightarrow x \leftrightarrow y \dots,每次长度+2)

avatar
zc
2020-04-27 17:49:00
查看原题

点击跳转

可以发现,这条链必然经过每个给定点的父亲

把每个给定点都变成它的父亲

按深度排序

依次判断接下来的节点是否在上一个的子树中即可

2/2
Search
search