题意 给出一棵n个节点的带标号树，要求对于每个k，求出有多少棵生成树满足恰好有k条边与原树相同。
n<=100
分析 【树形dp|Codeforces 917D Stranger Trees 树形dp+容斥原理】一开始的想法是，设g[k]表示在原树中任意选择k条边，必然包含这k条边的生成树的数量的和。求出g[k]后，很容易通过一个O(n^2)的容斥来求出答案。
问题在于怎么求g[k]。
设我们选择了k条边，那么原树中就只剩下n-k个连通块，记第i个连通块的大小为G[i]。
在prufer序列中，每个位置可以放m个连通块中的一个，然后选择连通块中的任意一个点来连边，这样就有 (∑G[i])n?k?2=nn?k?2( ∑ G [ i ] ) n ? k ? 2 = n n ? k ? 2 种方案。
但我们只决定了边的一端连的什么，另一边假设连的是第j个连通块，那么也有G[j]种连边方案。于是上面的式子再乘上 ∏G[i]∏ G [ i ] 就是一种选边方式的贡献了。
然后我们就可以开始dp，设f[i,j,k]表示以i为根的子树中，选出了j个连通块，i所在的连通块大小为k的答案，每次枚举儿子的j和k进行转移。通过树形dp的复杂度分析不难发现这样做的复杂度是O(n^4)。
然后就做完了。
代码
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int N=105;
const int MOD=1000000007;
int n,size[N],cnt,last[N],jc[N],ny[N],f[N][N][N],g[N],tmp[N][N];
struct edge{int to,next;
}e[N*2];
void addedge(int u,int v)
{
e[++cnt].to=v;
e[cnt].next=last[u];
last[u]=cnt;
e[++cnt].to=u;
e[cnt].next=last[v];
last[v]=cnt;
}int ksm(int x,int y)
{
int ans=1;
while (y)
{
if (y&1) ans=(LL)ans*x%MOD;
x=(LL)x*x%MOD;
y>>=1;
}
return ans;
}void mod(int &x) {x-=x>=MOD?MOD:0;
}int C(int n,int m)
{
return (LL)jc[n]*ny[m]%MOD*ny[n-m]%MOD;
}void dp(int x,int fa)
{
size[x]=1;
f[x][1][1]=1;
for (int i=last[x],to=e[i].to;
i;
i=e[i].next,to=e[i].to)
{
if (to==fa) continue;
dp(to,x);
for (int j=1;
j<=size[x];
j++)
for (int k=1;
k<=size[x];
k++)
{
if (!f[x][j][k]) continue;
for (int j1=1;
j1<=size[to];
j1++)
for (int k1=1;
k1<=size[to];
k1++)
{
mod(tmp[j+j1][k]+=(LL)f[x][j][k]*f[to][j1][k1]%MOD*k1%MOD);
mod(tmp[j+j1-1][k+k1]+=(LL)f[x][j][k]*f[to][j1][k1]%MOD);
}
}
size[x]+=size[to];
for (int j=1;
j<=size[x];
j++)
for (int k=1;
k<=size[x];
k++)
f[x][j][k]=tmp[j][k],tmp[j][k]=0;
}
}int main()
{
scanf("%d",&n);
jc[0]=ny[0]=jc[1]=ny[1]=1;
for (int i=2;
i<=n;
i++) jc[i]=(LL)jc[i-1]*i%MOD,ny[i]=(LL)(MOD-MOD/i)*ny[MOD%i]%MOD;
for (int i=2;
i<=n;
i++) ny[i]=(LL)ny[i-1]*ny[i]%MOD;
for (int i=1;
i=0) g[i]=(LL)g[i]*ksm(n,n-i-2)%MOD;
}
for (int i=0;
i 推荐阅读
- HDU 5519 Kykneion asma（沈阳站K题&&DP+容斥）
- 解题报告|51nod 1667 概率好题
- Codeforces Round #275 (Div. 1)D（树形DP）
- Codeforces Round #277 (Div. 2)D（树形DP计数类）
- online|hdu5834Magic boy Bi Luo with his excited tree
- online|bzoj2286: [Sdoi2011消耗战
- #|Codeforces Round #530 (Div. 2) F. Cookies（树形DP+线段树）
- DP|[codeforces 917D]Stranger Trees
- 容斥原理|【WC2017模拟1.22】简单题