TreeUnion

作者：聂恺辰 徐明宽

关键词：计数 概率 树形DP

题目简述

用字符串形式给出两棵大小为$N$的树，然后随机生成一个排列$1 \sim N$的排列$P$，令第一棵树的点$i$与第二棵树的点$P_{i}$连边

求期望这个图中有多少个长度为$K$的环

数据范围

$N \leq 300，K \leq 7$

算法

由于$K \leq 7$，且每个点只与另一棵树上的一个节点相连，所以这个环一定是树A->树B->树A这种形式。

也就是说，这个环一定恰好经过两条非原树边，即经过$K-2$条树边

这样我们可以分别求出对于每棵树有多少点对$(A,B)$使得$dis(A,B)==1,2,3,4$。

然后令两棵树的A相连，B相连，发生的概率为$\frac{1}{\binom{n}{2}} = \frac{2}{N(N-1)}$（因为这等价于A的两个端点这个集合恰好对应了B的两个端点这个集合）。

接下来枚举两棵树上分别经过了多少边，把两边答案乘起来再累加就可以了

至于如何求点对数量，反正$N$很小，暴力做就可以。另外也可以写树形DP，求出每个点的$1,2,3,4$层儿子个数，就可以在$O(NK^2)$的时间内统计点对数量了。