Codeforces 161D Distance in Tree(树型DP)
2024-09-07 19:01:18
题目链接 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 ; }
最新文章
- JAVA中关于锁机制
- Java课程设计——扫雷(winmine)
- 【性能诊断】StackOverflow引发的“网络”及系统稳定性问题
- RabbitMQ的work queue(1)
- Python自动化 【第一篇】:Python简介和入门
- 基于deb包快速搭建内外apt源
- 身份证校验程序(上)- 零基础入门学习Delphi48
- MySql事务无法回滚的原因
- [CQOI 2015]选数
- anaconda的scikit-learn报错It seems that scikit-learn has not been built
- SpingMVC的工作流程
- JVM与GC
- MySQL技术内幕读书笔记(五)——索引与算法
- Spring 学习笔记(十)渲染 Web 视图 (Apache Tilesa 和 Thymeleaf)
- 6.form表单四种提交方式
- ANSI C 常见宏的使用
- java 异常的限制
- Backbone学习笔记 - Model篇
- JAVA 方法 和Scanner
- HDU3535——AreYouBusy
热门文章
- WPF触控程序开发(四)——MultiTouchVista_-_second_release_-_refresh_2的救赎
- Java面向对象---方法递归调用
- BZOJ 4971: [Lydsy1708月赛]记忆中的背包
- 获取获取docker的文件
- VC下如何调用控制台命令以及其他可执行文件
- Asp.net自定义控件开发任我行(6)-嵌入资源下
- 如何部署安装软件:vs2010 &#39;VS&#39; Inno Setup
- STL学习笔记6 -- 栈stack 、队列queue 和优先级priority_queue 三者比较
- Ecplise实战常用操作快捷键(更新至2018年10月8日 13:46:40)
- LuffyCity-MySQL综合练习50实例