题目链接 Distance in Tree

$k <= 500$ 这个条件十分重要。

设$f[i][j]$为以$i$为子树,所有后代中相对深度为$j$的结点个数。

状态转移的时候,一个结点的信息由他的儿子转移过来。

那么一边进行状态转移,一边统计答案即可。

 #include <bits/stdc++.h>

 using namespace std;

 int f[][], deep[];
vector <int> v[];
int n, k, x, y;
long long ans; void dfs(int x, int fa, int dep){
int c[];
deep[x] = dep;
for (auto u : v[x]){
if (u == fa) continue;
dfs(u, x, dep + );
memset(c, , sizeof c); c[] = ;
for (int i = ; i <= k; ++i) c[i + ] = f[u][i];
for (int i = ; i <= k - ; ++i) ans += (long long)f[x][i] * c[k - i];
for (int i = ; i <= k; ++i) f[x][i] += c[i];
}
} int main(){ ans = ;
scanf("%d%d", &n, &k);
for (int i = ; i <= n - ; ++i){
scanf("%d%d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
} memset(deep, , sizeof deep);
dfs(, , );
for (int i = ; i <= n; ++i) if (deep[i] >= k) ++ans;
printf("%lld\n", ans); return ; }

最新文章

  1. JAVA中关于锁机制
  2. Java课程设计——扫雷(winmine)
  3. 【性能诊断】StackOverflow引发的“网络”及系统稳定性问题
  4. RabbitMQ的work queue(1)
  5. Python自动化 【第一篇】:Python简介和入门
  6. 基于deb包快速搭建内外apt源
  7. 身份证校验程序(上)- 零基础入门学习Delphi48
  8. MySql事务无法回滚的原因
  9. [CQOI 2015]选数
  10. anaconda的scikit-learn报错It seems that scikit-learn has not been built
  11. SpingMVC的工作流程
  12. JVM与GC
  13. MySQL技术内幕读书笔记(五)——索引与算法
  14. Spring 学习笔记(十)渲染 Web 视图 (Apache Tilesa 和 Thymeleaf)
  15. 6.form表单四种提交方式
  16. ANSI C 常见宏的使用
  17. java 异常的限制
  18. Backbone学习笔记 - Model篇
  19. JAVA 方法 和Scanner
  20. HDU3535——AreYouBusy

热门文章

  1. WPF触控程序开发(四)——MultiTouchVista_-_second_release_-_refresh_2的救赎
  2. Java面向对象---方法递归调用
  3. BZOJ 4971: [Lydsy1708月赛]记忆中的背包
  4. 获取获取docker的文件
  5. VC下如何调用控制台命令以及其他可执行文件
  6. Asp.net自定义控件开发任我行(6)-嵌入资源下
  7. 如何部署安装软件:vs2010 &#39;VS&#39; Inno Setup
  8. STL学习笔记6 -- 栈stack 、队列queue 和优先级priority_queue 三者比较
  9. Ecplise实战常用操作快捷键(更新至2018年10月8日 13:46:40)
  10. LuffyCity-MySQL综合练习50实例