首页 > 代码库 > CF263（D1）B 树形DP
CF263（D1）B 树形DP
【题意】：
给出一张无向图，图中每个点着有颜色（1或者0），问有多少种不同的切割方法，使切割后每一块区域恰有一个黑点。
【知识点】：
树形DP
【题解】：
dp方程声明如下
dp[u][0]：表示以跟节点为u的树，有多少种切割方法，使切成若干个区域后，u所在的区域为唯一一个没有黑点的区域。
dp[u][1]：表示以跟节点为u的树，有多少种切割方法，使切割后的每个区域（包括u所在的区域）恰有一个黑点。
那么当u点为黑点时
dp[u][0]=0。 dp[u][1]=若干个（dp[v][0] + dp[v][1]）的乘积。
u为白色节点时
dp[u][0]=若干个（dp[v][0] + dp[v][1]）的乘积。 dp[u][1]=若干个(dp[v][1]与其它子节点（dp[v][0] + dp[v][1]）的乘积)的和。
叙述并不是很清楚，有待改进，因为自己思路也一直模模糊糊的。
【代码】：
1 #include <map> 2 #include <set> 3 #include <cmath> 4 #include <ctime> 5 #include <queue> 6 #include <stack> 7 #include <cstdio> 8 #include <string> 9 #include <vector>10 #include <cstring>11 #include <sstream>12 #include <iostream>13 #include <algorithm>14 #include <bitset>15 #include <climits>16 using namespace std;17 18 #define wh while19 #define inf (int)(~0u/2)20 #define FOR(i, n) for(int i = 0; i < n; i++)21 #define FOR1(i, n) for(int i = 1; i < n; i++)22 #define FOR2(i, n) for(int i = 0; i <= n; i++)23 #define REP(i,n) for(int i = 1; i <= n; i++)24 #define FORI(it,n) for(typeof(n.begin()) it = n.begin(); it != n.end(); it++)25 #define sf scanf26 #define pf printf27 #define frs first28 #define sec second29 #define psh push_back30 #define mkp make_pair31 #define PB(x) push_back(x)32 #define MP(x, y) make_pair(x, y)33 #define clr(abc,z) memset(abc,z,sizeof(abc))34 #define lt(v) v << 135 #define rt(v) v << 1 | 136 //#define mid ((l + r) >> 1)37 #define lson l, mid, v << 138 #define rson mid + 1, r, v << 1 | 139 40 #define fre freopen("1.txt", "r", stdin)41 42 typedef long long LL;43 typedef long double LD;44 45 const int MOD = 1e9 + 7;46 47 const int maxn = 1e5 + 100;48 int dp[maxn][2];49 int val[maxn];50 vector<int> G[maxn];51 int add(int a, int b){52 return (a + b) % MOD;53 }54 int mul(int a, int b){55 return a * (LL)b % MOD;56 }57 void dfs(int u){58 dp[u][val[u]] = 1; dp[u][val[u] ^ 1] = 0;59 FOR(i, (int)G[u].size()){60 int v = G[u][i];61 dfs(v);62 int last0 = dp[u][0], last1 = dp[u][1];63 dp[u][0] = mul(last0, add(dp[v][0], dp[v][1]));64 dp[u][1] = add(mul(last0, dp[v][1]),65 mul(last1, add(dp[v][0], dp[v][1])));66 }67 }68 69 int main(){70 int n;71 wh(sf("%d", &n) != EOF){72 FOR(i, n) G[i].clear();73 FOR(i, n - 1){74 int tmp; sf("%d", &tmp);75 G[tmp].PB(i + 1);76 }77 FOR(i, n) sf("%d", &val[i]);78 dfs(0);79 pf("%d\n", dp[0][1]);80 }81 }
CF263（D1）B 树形DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。