CF814E An unavoidable detour for home

An unavoidable detour for home

Solution

由最短路唯一,不难发现以下性质:

1、原图可以通过对于$1$号点的最短路长度分层,成一棵树的形式,每一层的最短路长度相同。

2、剩下的边只能在树的同层内的点加。

3、由于要求对于$i>j$有$dis_i>dis_j$,所以每一层是一段区间。

于是,我们就可以$DP$了。显然有一个暴力的做法,$f[i][pre_1][pre_2][now_1][now_2]$表示上一层剩下的度数为$1$的点有$pre_1$个,度数为$2$的点有$pre_2$个。这一层的对应分别有$now_1,now_2$个。转移讨论一下$i$号点的连边情况。当$pre_1=pre_2=0$时,这一层就填完了,该填到下一层。

显然是可以通过预处理同层里的方案数直接每层转移。注意到度数为$2$的点的方案数要提前除$2$。

同时注意到,数据范围只有$50$,所以好写$n^5$暴力就可以愉快通过了。真好写

BZOJ3625小朋友与二叉树

小朋友与二叉树

Solution

对$C$这一维做一个生成函数,易得$C(x)=\sum_{i\in S}x^i$

然后我们在考虑二叉树,对于二叉树做一个生成函数$F(x)$。

我们不难发现
$$
F(x)=C(x)F^2(x)+1
$$
为什么是这样呢?我们考虑左右儿子合并在一起之后就是$F^2(x)$再加上根自己的贡献就是$F^2(x)C(x)$,然后我们发现常数项没有了,所以最后$+1$表示空树。

然后我们就可以愉快的解方程了,通过求根公式可以得到
$$
F(x)=\frac{1\pm\sqrt{1-4C(x)}}{2C(x)}
$$
其中有一个$\pm$该怎么办呢?通过简单观察我们可以发现,分母的常数项为$0$。如果是$+$,那么开根号后得到的多项式的常数项一定是一个非负数,所以这样分子就一定会有常数项,那么整个分数就一定会有余数。故上面只能为$-$。

于是我们就可以通过之前介绍过的多项式开根和多项式求逆元解决这道题了。