首页 > 代码库 > Codeforces Round #277 (Div. 2)Valid Sets 树DP
Codeforces Round #277 (Div. 2)Valid Sets 树DP
题意：给出一棵树，并给出每个节点上的权值，求有多少个连通子块的最大值与最小值的差不超过d。
对于每个顶点建立一颗树，然后找比它价值大的 或者 价值相等且之前没有被当作顶点建立树的点，这样就避免重复了。
dp[x]表示包涵x且以x为顶点的连通子树的个数，dp[x] = ∏ (dp[son[x]] + 1)。
注意要用long long 。
#include<iostream>#include<iostream>#include<cstdio>#include<cstring>#include<map>#include<vector>#include<stdlib.h>#include<algorithm>using namespace std;typedef long long LL;LL d;const LL maxn = 2222;const LL mod = 1000000007;struct Node{ LL next; LL to;}e[maxn * 2];LL len;LL head[maxn];LL dp[maxn];LL father[maxn];LL vis[maxn];void add(LL from, LL to){ e[len].to = to; e[len].next = head[from]; head[from] = len++;}void build(LL root, LL pre){ father[root] = pre; for (LL i = head[root]; i != -1; i = e[i].next){ LL cc = e[i].to; if (cc == pre) continue; build(cc, root); }}LL val[maxn];void dfs(LL x, LL root){ dp[x] = 0; LL ans = 1; for (LL i = head[x]; i != -1; i = e[i].next){ LL cc = e[i].to; if (cc == father[x])continue; if (val[cc] == val[root] && vis[cc]) continue; if (val[cc]<val[root] || val[cc] - val[root]>d) continue; // prLLf("%I64d %I64d\n",cc,val[cc]);system("pause"); dfs(cc, root); ans *= dp[cc] + 1; ans %= mod; } dp[x] += ans; dp[x] %= mod;}int main(){ LL n; cin >> d >> n; len = 0; memset(head, -1, sizeof(head)); memset(vis, 0, sizeof(vis)); for (LL i = 1; i <= n; i++) scanf("%I64d", &val[i]); for (LL i = 1; i<n; i++){ LL a; LL b; scanf("%I64d%I64d", &a, &b); add(a, b); add(b, a); } LL ans = 0; for (LL i = 1; i <= n; i++){ build(i, i); dfs(i, i); ans += dp[i]; vis[i] = 1; ans %= mod; // prLLf("%I64d\n",dp[i]); } cout << ans << endl; return 0;}
Codeforces Round #277 (Div. 2)Valid Sets 树DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。