A6001 | 数树上块
时间限制2s
内存限制512MB
通过 / 提交0/0
题目描述
给定一棵含有 $n$ 个节点，编号为 $1\sim n$ 的无边权无根树和一个常数 $k$，求出这棵树的直径不超过 $k$ 的非空导出子图数目。
即，需要选出至少一个节点，满足任意两个被选中节点路径上的所有点也必须被选中，且它们的距离不超过 $k$，需要求出选点的方案数。
两点之间的距离定义为两点简单路径上的边数，两个方案不同当且仅当存在某个点，在一个方案中被选中，而在另一个方案中未被选中。
只需要输出答案对 $998244353$ 取模的结果。
即，需要选出至少一个节点，满足任意两个被选中节点路径上的所有点也必须被选中，且它们的距离不超过 $k$，需要求出选点的方案数。
两点之间的距离定义为两点简单路径上的边数，两个方案不同当且仅当存在某个点，在一个方案中被选中，而在另一个方案中未被选中。
只需要输出答案对 $998244353$ 取模的结果。
输入格式
包含 $n$ 行。
第 $1$ 行输入两个正整数 $n,k$，意义见题目描述。
第 $2\sim n$ 行，每行输入两个正整数 $u,v$，表示节点 $u,v$ 之间有一条边。
第 $1$ 行输入两个正整数 $n,k$，意义见题目描述。
第 $2\sim n$ 行，每行输入两个正整数 $u,v$，表示节点 $u,v$ 之间有一条边。
输出格式
包含一行，仅一个自然数，表示符合条件的方案数对 $998244353$ 取模的结果。
输入输出样例
输入 #1
5 2 1 2 1 3 3 4 3 5
输出 #1
14
共 $20$ 个测试点。
对于测试点 $1\sim 4$，满足 $n\le 15$；
对于测试点 $5\sim 10$，满足 $n\le 2\times 10^3$；
对于测试点 $11\sim 12$，满足 $k=n-1$；
对于测试点 $13\sim 20$，满足 $n\le 5\times 10^5$；
对于所有数据，满足 $1\le k< n\le 5\times 10^5$，保证输入会给出一棵无根树。
对于测试点 $1\sim 4$，满足 $n\le 15$；
对于测试点 $5\sim 10$，满足 $n\le 2\times 10^3$；
对于测试点 $11\sim 12$，满足 $k=n-1$；
对于测试点 $13\sim 20$，满足 $n\le 5\times 10^5$；
对于所有数据，满足 $1\le k< n\le 5\times 10^5$，保证输入会给出一棵无根树。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？