T3 Vladislav and a Great Legend (CF1097G)

· · 个人记录

T3 Vladislav and a Great Legend (CF1097G)

人生中第一道黑题

对我来说有点过于复杂与难以理解了，可能理解得不是很透彻

花了我一整天，我太弱了

CF传送门

洛谷传送门

题意简述

给你一棵有 n 个节点的树 T，n 个节点编号为 1 到 n 。

对于 T 中每个非空的顶点的集合 X ，令 f(X) 为包含 X 中每个节点的最小连通子树的最小边数，即虚树的大小。

再给你一个整数 k 。你需要计算对于每一个顶点的集合 X ，(f(X))^{k} 之和，即：

\sum\limits_{X \subseteq\{1,2, \ldots, n\}, X \neq \varnothing}(f(X))^{k}
数据范围
2 \leq n \leq 10^5 1 \leq u \leq v \leq n 1 \leq k \leq 200
题解

前铺知识

树形依赖背包

[复杂版]{https://blog.csdn.net/wt_cnyali/article/details/76649037}

题意：在一棵有根树上，每个节点都挂着一个物件有 w_i 的价值和 c_i 的体积

选出一个包含根节点的连通块，使得体积之和不超过背包大小 k ，价值之和最大。

[简化版]{https://www.cnblogs.com/water-mi/p/9818622.html}

题意：给定一棵有 n 个节点的点权树，要求你从中选出 m 个节点，使得这些选出的节点的点权和最大。

即每个节点的体积均为1

--下面是解法--

我们可以仿照背包的思想

只不过在这里不是一个整体的背包，而是每个节点上都有一个背包

转移过程相当于把每个子节点当做一个物品，一个一个加进去

其他都与背包一样的

这道题用到的是树形依赖背包的思想

第二类斯特林数

[第二类斯特林数]{https://www.cnblogs.com/gzy-cjoier/p/8426987.html}

定义：第二类斯特林数 S(n,m) 表示的是把 n 个不同的小球放在 m 个相同的盒子里方案数。

求法：S(n, m)=S(n-1, m-1)+m S(n-1, m)

考虑有 n-1 个小球，现在再放一个小球

如果新开一个，那就是 S(n-1, m-1) \Rightarrow S(n, m)

如果放到已有的盒子里，有 m 种选择，即 m S(n-1, m) \Rightarrow S(n, m)

性质：n^{k}=\sum\limits_{i=0}^{k} S(k, i) \times i ! \times C(n, i)

但这样放会有一些盒子是空的，于是用 $i$ 枚举有多少个盒子是非空的 确定到底是哪 $i$ 个盒子是非空的，要乘上 $C(n, i)

把k个不同的小球放入 i 个相同的盒子里要 S(k, i)

但这里盒子是不同的，因此再乘上 i!

思路

首先，看到要算的东西里有个大大的 k 次方

而且 k 还很小

可以考虑用第二类斯特林数的那个性质转化

n^{k}=\sum\limits_{i=0}^{k} S(k, i) \times i ! \times C(n, i)

于是

\sum(f(X))^{k}=\sum \sum\limits_{i=0}^{k} S(k, i) \times i ! \times C(f(X), i)

交换和号

=\sum\limits_{i=0}^{k} S(k, i) \times i ! \times \sum C(f(X), i)

噢！

发现其实左边的东西都是可以很快算出来的

因此实际要算的是

\sum C(f(X), i)

于是我们把难以处理的幂换成了组合数

但这样直接去考虑好像和幂没有什么区别

不妨从整体来考虑

考虑它的实际意义，其实就是 对于每个生成树，从 f(X) 选出 i 条边涂色的方案数之和

选出 i 条边，像不像前面提到的树形依赖背包？

一个一个点来转移

解决了？

做法

NO

这题真正的难点不在于思路，在于接下来的实现

仿照树形依赖背包，设 dp[i][j] 表示以 i 为根节点的子树中，所有 点集形成的生成树 中涂j条边的方案数

请注意是 所有点集形成的生成树 （即要求的）而不是 所有生成树

请注意是所有而不是经过 i 节点的

我们是从边的角度来考虑的

也就是说，存在一种特殊情况

只连一棵子树（因为连了多棵子树就合法了），不选根节点而选它连向子节点的边

会被转移，但不会被计入答案

这种情况显然是不合法的，又不选 $o$ ，却选了这条边 但是我们稍后在上面转移时需要它，因为是虚树，在上面就不需要选中这个 $o$ 点了 （这大概是最难理解的部分） ~~讲个定义都已经把要点讲了一半了~~ 来个状态转移方程： $dp[o][k]=dp[o][i] \times dp[v][k-i] (0 \leq i \leq k)

很好理解，就是在前面的点里先选 i 条涂色，再在这颗子树里选 k-i 条涂色

当然为了好写实际上是这样写的

dp[o][i+j]=dp[o][i] \times dp[v][j] (0 \leq i \leq k, 0 \leq j \leq k-i)

理解到这可能又会冒出一个问题

这是按边来转移的，所以转移到父节点时，又不 +1 ，岂不是漏了 o 与 fa(o) 之间的边了吗？

当然其实可以连，也可以不连

所以dp完后还要把 dp[o][i] 变为 dp[o][i]+dp[o][i-1]

最后一个问题

如何初始化？

dp[o][0]=2

因为选了 o ，还是不选 o ，都是 0 条边

所以有两种情况

于是有一个东西不能转移

就是初始化时 o 不选的情况，总不能转移个空集吧

所以还得减 1

看起来是 O(nk^2) 的

其实是 O(nk) 的

复杂度证明我也搞不明白就不放上来了

注意事项

· 很难理解，请结合题解与代码，仔细思考，不要着急

AC代码

#include<bits/stdc++.h>
using namespace std;
const long long N=1e5+5,mod=1e9+7;
struct nod{
    long long to,nxt;
}e[2*N];
long long head[N],cnt;
void add(long long u,long long v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
long long n,k;
long long dp[N][205],f[N],size[N],ans[N],S[205][205];
void dfs(long long o,long long fa){
    size[o]=1,dp[o][0]=2;//初始化，dp[o][0]：选o还是不选o都是0条边（后面会处理这种情况） 
    for(long long i=head[o];i;i=e[i].nxt){
        long long v=e[i].to;
        if(v==fa) continue;
        dfs(v,o);
        for(long long i=0;i<=k;i++) f[i]=0;
        for(long long p=0;p<=min(k,size[o]);p++)
            for(long long q=0;q<=min(k-p,size[v]);q++)
                f[p+q]=(f[p+q]+(dp[o][p]*dp[v][q])%mod)%mod;
        //类似背包，f为临时数组避免混用 
        for(long long j=0;j<=k;j++) dp[o][j]=f[j];
        //把答案从f转移到dp[o] 
        for(long long j=0;j<=k;j++) ans[j]=(ans[j]+mod-dp[v][j])%mod;
        //这一步其实可以放到后面，ans要减掉不经过o的情况，这里先减了（为了好写） 
        size[o]+=size[v];
    }
    for(long long i=0;i<=k;i++) ans[i]=(ans[i]+dp[o][i])%mod;
    //累加答案，前面已经减过多余的答案了 
    for(long long i=k;i>=1;i--) dp[o][i]=(dp[o][i]+dp[o][i-1])%mod;
    //考虑o的父亲，那么显然i条会变成i+1条，于是dp[o]整体往右移一格 
    dp[o][1]=(dp[o][1]+mod-1)%mod;
    //减掉最前面不选o的情况（无法转移至父节点） 
}
int main(){
    scanf("%lld%lld",&n,&k);
    for(long long i=1;i<=n-1;i++){
        long long u,v;
        scanf("%lld%lld",&u,&v);
        add(u,v),add(v,u); 
    }
    dfs(1,0);
    S[0][0]=1;
    for(long long i=1;i<=k;i++)
        for(long long j=1;j<=i;j++)
            S[i][j]=(S[i-1][j-1]+(S[i-1][j]*j)%mod)%mod;
    //计算第二类斯特林数 
    long long tmp=1,sum=0;
    for(long long i=1;i<=k;i++) tmp=(tmp*i)%mod,sum=(sum+(tmp*S[k][i])%mod*ans[i])%mod; 
    //计算答案 
    printf("%lld",sum);
}