首页 > 试题广场 >

蓝魔法师

[编程题]蓝魔法师
  • 热度指数：5 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
“你，你认错人了。我真的，真的不是食人魔。”--蓝魔法师

给出一棵树，求有多少种删边方案，使得删后的图每个连通块大小小于等于k，两种方案不同当且仅当存在一条边在一个方案中被删除，而在另一个方案中未被删除，答案对998244353取模

输入描述:
第一行两个整数n,k, 表示点数和限制
2 <= n <= 2000, 1 <= k <= 2000
接下来n-1行，每行包括两个整数u,v，表示u,v两点之间有一条无向边
保证初始图联通且合法


输出描述:
共一行，一个整数表示方案数对998244353取模的结果
示例1

输入

5 2
1 2
1 3
2 4
2 5

输出

7
算法知识视频讲解
开通博客
头像 lifehappy
发表于 2020-08-04 15:49:54
蓝魔法师 思路 树上问题求方案数，考虑树形，我们设置表示，当节点联通块数量是时，以为根节点的树上的方案数量。 显然我们可以做一个树上背包来枚举节点的连接情况，每次遍历一颗子树时枚举，要注意背包的枚举顺序均要从大到小开始枚举。 最后再特判一个不与这颗子树相连的特殊情况，也就是。 代码 /* Aut 展开全文
去ta的博客 赞 (11) 回复(0) 收起
头像 CoolGuang!
发表于 2020-08-05 01:56:30
考虑树形dp与组合数学结合 定义dp状态 dp(i,k) 代表 i的子树全部合法且i的连通块大小是k 那么显然对于任意一个节点u来说初始:dp[u][1] = 1 接下来枚举每一条边，对于一条边来言有删除与不删除两种状态： 1.删除： 删除此边，那么就意味着当前以u节点连通块大小为k的方案数 都可以 展开全文
去ta的博客 赞 (6) 回复(1) 收起
头像 zzugzx
发表于 2020-08-04 19:27:51
题目链接 题意：题解： AC代码 /* Author : zzugzx Lang : C++ Blog : blog.csdn.net/qq_43756519 */ #include<bits/stdc++.h> using namespace std; #d 展开全文
去ta的博客 赞 (4) 回复(2) 收起
头像 sunsetcolors
发表于 2020-08-04 15:54:04
蓝魔法师 题目地址： https://ac.nowcoder.com/acm/problem/20811 基本思路： 考虑树形,我们用表示在以为根的子树中,包含且连通块大小为的方案数,考虑在以每一个节点为根的情况,我们对于它的每一棵子树进行转移,我们假设已经对之前的几个子树做完了处理,那么在 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 shyyhs
发表于 2021-03-05 19:28:43
思路 思路应该算是比较简单吧...难点在于时间复杂度的证明.因为这题和的范围都是以内的.题目是让你切成若干份,每份大小都不超过,因为是一棵树,所以很容易想到树形.对于树形,我们很容易想到利用子树就行转移.那么我们要转移什么,才能让子树来跟新父节点呢?很显然的一个东西,我可以和子树分割,也可以不和子树 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 hnust_yangyanjun
发表于 2020-08-12 16:03:48
题意： 给与一棵树，求有多少种删边方案，使得删后的图每个连通块大小小于等于k，两种方案不同当且仅当存在一条边在一个方案中被删除，而在另一个方案中未被删除，答案对998244353取模。 思路：树形dp：从叶子节点向根转移，dp[i][j]表示以i为根的树删边时i处于的连通块大小为j的方案数。sum 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 瑜画
发表于 2020-08-18 21:54:16
用dp[j][k]表示j结点的连通块 大小为k的方案数然后从叶子结点一路递推回来，分类讨论。如果不切掉连着的边，两个连通块合并，方案数就是直接相乘dp[u][j+k]= dp[u][j]*dp[to][k]如果切掉连着的边，方案数就是独立的那么就是加上孩子的dp和，dp[u][j]=dp[u][j] 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 鞠永全
发表于 2020-08-05 09:48:19
https://ac.nowcoder.com/acm/problem/20811参考：https://blog.nowcoder.net/n/a52f02e1f87844e494690964fc6959dc题意：给出一棵树，求有多少种删边方案给出一棵树，求有多少种删边方案使得删后的图每个连通块大小 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 horz
发表于 2020-08-07 17:48:23
题意 给出一棵树，求有多少种删边方案，使得删后的图每个连通块大小小于等于k，两种方案不同当且仅当存在一条边在一个方案中被删除，而在另一个方案中未被删除，答案对998244353取模。 分析 我们定义表示为i的子树的所有联通块大小不超过k，并且i所在联通块大小为j的方案数。 对于每条边，假设为 u — 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 998244353
发表于 2020-08-05 15:24:24
题意： 给定一棵个点的树，问有多少种删边方案使得删边后每个连通块大小不大于，两种方案不同当且仅当存在一条边在一个方案中被删除，而在另一个方案中未被删除，答案对取模数据范围： 题解 ：表示以为根，连通块的大小为的方案数。考虑的一个儿子： 和的边被断开，则的连通块大小对无影响， 与的边未被断开，则 展开全文
去ta的博客 赞 (0) 回复(0) 收起

问题信息

深度优先搜索(DFS) 树形dp
上传者：牛客301599号
难度：
0条回答 24浏览

热门推荐

通过挑战的用户

查看代码

相关试题

蓝魔法师

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号