Codeforces 486D Valid Sets (树型DP)
2024-10-21 03:34:30
题目链接 Valid Sets
题目要求我们在一棵树上计符合条件的连通块的个数。
满足该连通块内,点的权值极差小于等于d
树的点数满足 n <= 2000
首先我们先不管这个限制条件,也就是先考虑d为正无穷大的时候的情况。
我们要求出树上所有连通块的个数。
这个时候我们令f[i]为以i为根的子树中的连通块的数目。
此时状态转移方程为 f[x] = f[x] * (f[u] + 1)
其中f[x]初始值为1,u为x的儿子
最后f[1]的值(我们假设1为根结点)即为答案
时间复杂度为O(n)
注意到n只有2000,说明这题的时间复杂度不止O(n)
那么我们对于每一个点,以他的权值作为连通块的权值最小值。
于是就可以以他为根做一次DFS。
若DFS的过程中碰到权值比他小的点,或者权值减他的权值大于d的点,我们就不往这个点DFS下去。
但是有一种特殊情况
这样做可能导致重复计算
因为这样的方法会导致两个权值相同切且相连的点组成的连通块被计算多次。
于是我们对那些权值相同切且相连的点的边,定一个方向。
规定编号小的点能DFS到编号大,和他相连且权值和他相等的点
但是反过来就不行了。
这样规定了一个方向之后我们就消除了重复计算的问题。
时间复杂度 $O(n^{2})$
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i)
#define dec(i, a, b) for (int i(a); i >= (b); --i) typedef long long LL; const int N = 2010;
const LL mod = 1e9 + 7; vector <int> v[N];
int n, d, et, cnt;
int a[N];
LL f[N];
LL ans = 0; void dfs(int x, int fa){
LL now = 0;
f[x] = 1;
for (auto u : v[x]){
if (u == fa) continue;
if (a[u] > cnt + d || a[u] < cnt) continue;
if (a[u] == cnt && u < et) continue;
dfs(u, x);
(f[x] *= f[u] + 1) %= mod;
}
} int main(){ scanf("%d%d", &d, &n);
rep(i, 1, n) scanf("%d", a + i);
rep(i, 1, n - 1){
int x, y;
scanf("%d%d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
} rep(i, 1, n){
cnt = a[i]; et = i;
memset(f, 0, sizeof f);
dfs(i, 0);
(ans += f[i]) %= mod;
} printf("%lld\n", ans);
return 0;
}
最新文章
- 深度剖析 | 基于大数据架构的BI应用
- JCO事务管理
- live555源代码编译
- PIC和PIE
- Scala官方作弊条
- MySQL查看和修改字符编码
- VMware装ubuntu 进不去图形界面, 卡在Installing VMware Tools
- Cocos2d-x 3.1.1开发环境
- 前端开发chrome与fireFox浏览器都使用
- sass 学习
- 1000以内完全数(完美数)获取实现---基于python
- ASP.NET MVC 播放远程服务器上的MP3文件
- SEO优化-robots.txt解读
- 【学习笔记】分布式Tensorflow
- git tag 打标签
- windows下忘记mysql超级管理员root密码的解决办法(也适用于wamp)
- CentOS7 下安装 NFS,Linux/Windows 作为客户端
- 使用jquery操作session
- gozmq的安装与使用
- jenkins遇到含中文路径的SVN地址时认证通不过