「BZOJ 5346」树

Description

有$n$个点,它们从$1$到$n$进行标号,第$i$个点的限制为度数不能超过$A_i$
现在对于每个$s(1\leqslant s \leqslant n)$,问从这$n$个点中选出一些点组成大小为$s$的有标号无根树的方案数
$n\leqslant 100$



- 阅读全文 -

「BZOJ 5473」仙人掌

Description

有一个$n$个点,$m$个边的仙人掌。所谓仙人掌,就是任何一个点至多属于一个环。
每个边有$\frac 12$的概率被删掉。问期望剩下多少个边联通块。
所谓边联通块,就是问剩下的边,构成多少个联通块,单独一个点不算做联通块。
输出答案乘以$2m$之后$\bmod 1000000007$的结果。
$1\leqslant n\leqslant 1000000$





- 阅读全文 -

「BZOJ 5482」tree

Description

现在有一棵$n$个结点的树,对于点$i(i>1)$,它的父亲结点编号为$\lfloor \frac i2 \rfloor$。
现在有$m$只鸟,每只鸟有初始位置$p_i$。树上每个结点有最大容纳量$c_i$,表示这个结点最多能容纳的鸟的数量。定义移动一只鸟的代价为树上的距离。
现在询问,对于$k$从$1..m$,将前$k$只鸟移动位置使得满足每个结点上的鸟的个数不大于最大容纳量的最小代价。
$n, m \leqslant 3 \times 10^5$

Solution

「BZOJ 5479」tree

Description

给出一棵树,根节点为$1$
给出两个集合,集合由树上节点组成
从两个集合分别选出一个元素,求其LCA
问LCA的最大深度是多少
$n\leqslant 10^5$





- 阅读全文 -

「CometOJ Contest #5 E」迫真大游戏

Description

有一个$n$个点的环,有一个指针会从$1$号点开始向后扫描,每次扫描有$p$的概率删除当前点。询问每个点最后一个被删除的概率。
答案对$998244353$取模。$n\leqslant 200000$


- 阅读全文 -