[GDOI2018]滑稽子图

时间:2021-11-22 01:38:21

题目链接:【被和谐】

题目大意:对于一棵树$(V,E)$,对于$S\subset V$,$f(S)$为点集$S$的导出子图的边数。求$\sum_{S\subset V}f(S)^k$

这里的导出子图说的是,点集为S,边集为$\{(u,v)\in E|u,v\in S\}$的一个子图。


看到这个$k$次方,马上用斯特林数。

$$ans=\sum_{S\subset V}f(S)^k=\sum_{i=0}^ki!S(k,i)\sum_{S\subset V}{f(S)\choose i}$$

然后考虑怎么求后面那个式子。

这个式子表示在$S$的导出子图里面选$i$条边的方案数,然后就可以树形dp了

设$dp_{x,s,0/1}$表示在以$x$为根的子树内部,选择$s$条边,$x$是否$\in S$的答案。

在新加上一个$x$的子树$v$的时候,$S$只有原来只有新的子树的情况直接加上就行。

还有合在一起的情况,设原来的子树有$j$条边,$v$里面有$k$条边。

则$$dp[x][j+k][0]+=(dp[v][k][0]+dp[v][k][1])*dp[x][j][0]$$$$dp[x][j+k][1]+=(dp[v][k][0]+dp[v][k][1]+[k\not= 0]dp[v][k-1][1])*dp[x][j][1]$$

上面那里为什么要加$dp[v][k-1][1]$呢?因为这时$x$和$v$都在点集里,可以选择$(x,v)$这条边。

注意合在一起的情况还要统计进答案里。

而且由于会出现贡献到自己的情况,所以要用一个辅助数组来存储。

 #include<cstdio>
#include<cstring>
#define Rint register int
using namespace std;
typedef long long LL;
const int N = , mod = ;
int n, m, K, head[N], to[N << ], nxt[N << ], size[N];
inline void add(int a, int b){
static int cnt = ;
to[++ cnt] = b; nxt[cnt] = head[a]; head[a] = cnt;
}
LL dp[N][][], f[][], ans[], S[][];
inline void dfs(int x, int fa){
size[x] = ;
dp[x][][] = ; dp[x][][] = ; ++ ans[];
for(Rint i = head[x];i;i = nxt[i])
if(to[i] != fa){
dfs(to[i], x);
memcpy(f, dp[x], sizeof f);
for(Rint j = ;j <= K && j <= size[to[i]];j ++)
f[j][] = (f[j][] + dp[to[i]][j][] + dp[to[i]][j][]) % mod;
for(Rint j = ;j <= K && j <= size[x];j ++)
for(Rint k = ;k <= K - j && k <= size[to[i]];k ++){
LL S = (dp[to[i]][k][] + dp[to[i]][k][]) % mod;
LL s1 = dp[x][j][] * S % mod, s2 = dp[x][j][] * (S + (k ? dp[to[i]][k - ][] : )) % mod;
f[j + k][] = (f[j + k][] + s1) % mod;
f[j + k][] = (f[j + k][] + s2) % mod;
ans[j + k] = (ans[j + k] + s1 + s2) % mod;
}
memcpy(dp[x], f, sizeof f);
size[x] += size[to[i]];
}
}
int main(){
scanf("%d%d%d", &n, &m, &K);
for(Rint i = ;i < n;i ++){
int a, b;
scanf("%d%d", &a, &b);
add(a, b); add(b, a);
}
dfs(, );
S[][] = ;
for(Rint i = ;i <= K;i ++)
for(Rint j = ;j <= i;j ++)
S[i][j] = (S[i - ][j - ] + S[i - ][j] * j) % mod;
LL fac = , res = ;
for(Rint i = ;i <= K;i ++){
fac = fac * i % mod;
res = (res + fac * S[K][i] % mod * ans[i] % mod) % mod;
}
printf("%lld", res);
}