【Nowcoder】蓝魔法师|树形dp、组合计数

题目链接&＃xff1a;https://ac.nowcoder.com/acm/problem/20811

题目大意&＃xff1a;

给出n个点的一棵树&＃xff0c;问有多少种删边方案使得删边后各连通块大小小于等于k&＃xff1f;

题目思路&＃xff1a;

考虑树形dp与组合数学结合

定义dp状态 dp(i,k) 代表 i的子树全部合法且i的连通块大小是k

那么显然对于任意一个节点u来说初始:dp[u][1] &＃61; 1

接下来枚举每一条边&＃xff0c;对于一条边来言有删除与不删除两种状态&＃xff1a;

1.删除&＃xff1a;

删除此边&＃xff0c;那么就意味着当前以u节点连通块大小为k的方案数 都可以 乘 v节点连通块大小所有的方案数&＃xff1a;