题目大意
给定一棵n个节点的树。对于k=0到n-1，输出有多少棵n个节点的带标号无根树恰好与给定的树有k条公共边。答案模 109+7
n≤100
分析
【DP|[codeforces 917D]Stranger Trees】我们从prufer序的角度考虑这道题。
选择了若干条原树的边后，我们得到一些联通块。把这些联通块都缩在一起，假设剩下m个点，接下来我们要去连接这些联通块，得到一棵树，然后考虑这棵树的prufer序是怎样的。
由于当前叶子的父亲所表示的联通块G中任意一个点都可能与叶子联通块相连，所以有 |G| 种可能。那么prufer序的m-2位共有 (∑mi=1|Gi|)m?2=nm?2 种可能情况。
但是prufer序不能完全表示这棵树，因为由prufer序只能确定父亲联通块中哪个点连了出去，不知道连到哪个点，假设叶子联通块是G’，那么还有 |G′| 种可能情况。再算上连接最后两个联通块的边的可能情况，所以上式还要乘上 ∏mi=1|Gi| 才能正确算出剩下m个联通块的答案。
知道上面的东西就可以dp了。设f[i][j][k]表示原树中以i为根的子树，分成了j个联通块（可以由此知道选了多少条原树的边），其中i所在联通块大小为k时的答案。转移时枚举儿子，然后枚举儿子的后两维。转移看起来有五重循环，但是可以通过树形背包的分析方法发现时间复杂度其实是 O(n4) 的
这样就做完了吗？没有！
我们发现这样算出来的是与原树至少有k条公共边的答案，需要一个 O(n2) 的容斥算出正确答案。这个就不具体写了。
#include
#include
#include using namespace std;
const int N=105,mo=1e9+7;
typedef long long LL;
int n,f[N][N][N],Size[N],g[N][N],ans,C[N][N],F[N],tot,h[N],e[N<<1],nxt[N<<1];
void Add(int x,int y)
{
e[++tot]=y;
nxt[tot]=h[x];
h[x]=tot;
}void dp(int x,int y)
{
Size[x]=1;
f[x][1][1]=1;
for (int i=h[x];
i;
i=nxt[i]) if (e[i]!=y)
{
dp(e[i],x);
memset(g,0,sizeof(g));
for (int j=1;
j<=Size[x];
j++)
{
for (int p=1;
p<=Size[x]-j+1;
p++) if (f[x][j][p])
{
for (int k=1;
k<=Size[e[i]];
k++)
{
for (int q=1;
q<=Size[e[i]]-k+1;
q++) if (f[e[i]][k][q])
{
g[j+k][p]=(g[j+k][p]+(LL)f[x][j][p]*f[e[i]][k][q]%mo*q)%mo;
g[j+k-1][p+q]=(g[j+k-1][p+q]+(LL)f[x][j][p]*f[e[i]][k][q])%mo;
}
}
}
}
Size[x]+=Size[e[i]];
memcpy(f[x],g,sizeof(g));
}
}int main()
{
scanf("%d",&n);
for (int i=1,x,y;
i 推荐阅读
- 题目|C. Ayoub and Lost Array（思维dp）
- HDU 5519 Kykneion asma（沈阳站K题&&DP+容斥）
- HDU 5185 Equation (DP)
- dp|AC Challenge(状态压缩DP)
- 解题报告|51nod 1667 概率好题
- 题解|【HNOI2017】大佬-dalao
- 树形dp|Codeforces 917D Stranger Trees 树形dp+容斥原理
- CodeForces - 1282B2 B2. K for the Price of One (Hard Version)