标签：连通 生活 vert limits 题解 sum times hzoi dp

生活在hzoi上 题解

考虑有两棵树怎么做，显然是 \(y^{n - k}=y^{n - \left\vert E_1 \cap E_2 \right\vert}\) 其中 \(E_1\) 和 \(E_2\) 是两棵树的边集

发现上边那个 \(k\) 是两棵树边集交构成的图的连通块个数 \(\left\vert E_1 \cap E_2 \right\vert\) 就是两棵树交的连通块数量的表示

因此有 \(k\) 个连通块的合法方案就是上面那一坨

考虑枚举连通块形态，也就是枚举重合的边，首先让边重合，之后任意连边使得连通块联通，这样就能构造出第二棵树，但是任意连边的时候会连上一些和第一条重合的边，导致连通块形态变化，这显然会算重

但是我们不会其他做法，把这个写出来，等等或许就有办法把算重的除去

贡献是

\[\sum_k \sum_{s_1 \cup s_2 \cup ... \cup s_k = E_1 ,s_1 \cap s_2 \cap ... \cap s_k = \varnothing} y^k n^{k-2} \prod \left\vert s_i \right\vert \]

右边 \(n^{k-2} \prod \left\vert s_i \right\vert\) 是 prufer 序列的结论

然后我们只要考虑怎么使用容斥或者什么其他玩意把多出来那部分搞掉就好了

jijidawang 做法

考虑这个东西实际上算了每个状态多少次，对于每个子状态，也就是从当前枚举的连通块里切断一些边，都会额外以错误的贡献算一遍当前状态，加上本来的一次贡献，所以是

\[\sum_{p \in Q} \sum_{i=0}^{n-k} \dbinom{n-k}{i} y^{k+i} \]

左边 \(p\) 是枚举每一棵合法的第二棵数，\(k\) 是这个状态和第一棵树交的连通块个数

整理一下，发现有个二项式定理展开形式，给它收回去，然后发现里面那个二项式系数没了

\[\sum\limits_{p \in Q} (1+y)^{n-k} y^{k} \]

也就是说当输入的那玩意是 y 的时候，上面那个算法算出来的是 $\sum\limits_{p \in Q} (1+y)^{n-k} y^{k} $

然而我们要求的是 $\sum\limits_{p \in Q} y^{k} $

假设现在我们能够对任意变量 \(x\) 求出 $\sum\limits_{p \in Q} (1+x)^{n-k} x^{k} $，而答案是 $\sum\limits_{p \in Q} y^{k} $

左边 \((1+x)^n\) 是好做式子，因此我们知道上面那个式子就能得知 $\sum\limits_{p \in Q} (1+x)^{-k} x^{k} $

发现我们构造一个合适的 \(x\) 使得 $\sum\limits_{p \in Q} (1+x)^{-k} x^{k}=\sum\limits_{p \in Q} y^{k} $ 即可

把 \((1+x)^n\) 提出来就是为了让这步好做些，容易知道 \(x=\frac{y}{1-y}\)

好了，现在设 \(f(x)=\sum\limits_k \sum\limits_{s_1 \cup s_2 \cup ... \cup s_k = E_1 ,s_1 \cap s_2 \cap ... \cap s_k = \varnothing} x^k n^k \prod \left\vert s_i \right\vert\)，为了好算和统一指数把 \(n^{-2}\) 提出来了

答案就是 $$\frac{f(x)}{(1+x)ⁿⁿ2}$$

dp

现在我们都有了计算答案的式子，只需要算出来 \(f(x)\) 就好了

如果枚举连通块个数的话是 \(O(n^2)\) 的，所以我们只能考虑将连通块的贡献扔到每个点里

这貌似是一个经典 trick，考虑这个式子相当于在每个连通块里面找一个点，将点权作为整个连通块的权值，之后整棵树的权值等于所有连通块权值的乘积

设状态 \(dp_{i,0/1}\) 分别是当前这个点所在连通块 选了/没选 的贡献，能够写出转移

\[dp_{i,1}=dp_{i,1} \times dp_{j,0} + dp_{i,0} \times dp_{j,1} + dp_{i,1} \times dp_{j,1} \]

\[dp_{i,0}=dp_{i,0} \times dp_{j,0} + dp_{i,0} \times dp_{j,1} \]

注意 \(dp_{i,1}\) 初值为 \(xn\)，先更新 \(dp_{i,1}\)，不然会出现一颗子树连了又没连

依次写出上面几项的含义：

1. \(dp_{i,1} \times dp_{j,0}\) 是和下面没选贡献节点的子树连到一起，所以选了自己
2. \(dp_{i,0} \times dp_{j,1}\) 是和当前子树连到一起，在子树内就选好贡献
3. \(dp_{i,1} \times dp_{j,1}\) 是不和当前子树连到一起，自己和子树都选好了贡献
4. \(dp_{i,0} \times dp_{j,0}\) 是和当前子树连一起
5. \(dp_{i,0} \times dp_{j,1}\) 是断开这条边

这样我们就能在 \(O(n)\) 的复杂度内求出 \(f(x)\) 从而解决此题

标签：连通,生活,vert,limits,题解,sum,times,hzoi,dp
From： https://www.cnblogs.com/hzoi-wang54321/p/18356606