题目链接:Codeforces 461B Appleman and Tree
题目大意:一棵树,以0节点为根节点,给定每个节点的父亲节点,以及每个点的颜色(0表示白色,1表示黑色),切断这棵树的k条边,使得树变成k+1个联通分量,保证每个联通分量有且仅有1个黑色节点。问有多少种分割方法。
解题思路:树形dp,dp[i][0]和dp[i][1]分别表示子树一下的分割方法中,i节点所在联通块不存在黑节点和已经存在一个黑节点的方案数。
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MOD = 1e9+7;
const int maxn = 1e5+5;
int N, v[maxn];
ll dp[maxn][2];
vector<int> g[maxn];
void init () {
memset(dp, 0, sizeof(dp));
int x;
scanf("%d", &N);
for (int i = 1; i < N; i++) {
scanf("%d", &x);
g[x].push_back(i);
}
for (int i = 0; i < N; i++)
scanf("%d", &v[i]);
}
ll pow_mod (ll x, int n, ll mod) {
ll ret = 1;
while (n) {
if (n&1)
ret = ret * x % mod;
x = x * x % mod;
n >>= 1;
}
return ret;
}
ll inv (ll x) {
if (x == 0)
return 1;
return pow_mod(x, MOD-2, MOD);
}
void solve (int u) {
if (g[u].size() == 0) {
dp[u][v[u]] = 1;
return;
}
for (int i = 0; i < g[u].size(); i++)
solve(g[u][i]);
if (v[u]) {
dp[u][0] = 0;
ll& ans = dp[u][1];
ans = 1;
for (int i = 0; i < g[u].size(); i++) {
int k = g[u][i];
ans = ans * (dp[k][1] + dp[k][0]) % MOD;
}
} else {
dp[u][1] = 0;
ll& ans = dp[u][0];
ans = 1;
for (int i = 0; i < g[u].size(); i++) {
int k = g[u][i];
ans = ans * (dp[k][0] + dp[k][1]) % MOD;
}
for (int i = 0; i < g[u].size(); i++) {
int k = g[u][i];
dp[u][1] += ans * inv(dp[k][0] + dp[k][1]) % MOD * dp[k][1] % MOD;
dp[u][1] %= MOD;
}
}
}
int main () {
init();
solve(0);
printf("%lld\n", dp[0][1] % MOD);
return 0;
}
分享到:
相关推荐
回头重新看了一下题意,这不就是求最长链的树形dp裸题吗? 代码如下: #include #define ll long long #define inf 0x3f3f3f3f #define mod 1000000007 #define PI acos(-1) #define fi first #define se second #...
Codeforces 1105B - Zuhair and Strings 测试点37个(全)
Codeforces - 1107B. Digital root & 1107C. Brutality(规律 & 贪心)Codeforces - 1107B.
暴枚最长桌脚的长度$l$,然后长度比$l$长的桌脚全部都要砍掉长度比$l$短的桌脚选择代价前$k$小的砍掉用线段树维护;示例程序 :typedef long l
Codeforces 题库 101-200 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
F. Maximum White Subtree ...You are given a tree consisting of n vertices. A tree is a connected undirected graph with n−1 edges. Each vertex v of this tree has a color assigned to it (av=1 if the
Codeforces 题库 001-100 共~500题 codeforces.com版权所有。 程序可提交至该网站评测。
codeforces编程网站预测分数插件
使用于Google Chrome的Codeforces Enhancer 1.1.2插件安装包。 版本:codeforces enhancer 1.1.2 使用浏览器:Google Chrome
Codeforces 185A - Plant 全测试点49个
codeforces 19 E Fairy 一道比较难的题目的解题报告 推荐阅读
题目分析:最优性问题,且是对区间操作的,而且数据范围满足 n^3 的时间复杂度,综上可以考虑区间dp,因为题目已经明确了需要求什么,所以我们不妨设 dp[ i ][ j ] 为区间 [ i , j ] 合并后的最短数列的长度,因为...
Codeforces global round 10 codes
编码 C ++中的Codeforce问题的解决方案
Codeforces round 678 division 2 codes
Some of the Codeforces problems codes
lucifer1004大佬的博客cf上分攻略故里大佬的githubcf思维题刷题数:44- (1421)codeforces 676 div2 A,B done
codeforces每日一题。 题意: 给出一个数组,让你挑选出能组成任意pair差值为2的幂的序列,并且使这个序列长度尽可能大。 思路: 针对于挑选出来的序列,任意pair对的差值为2的幂数。 假设有多个pair对,设dis(a,b)=2...
Codeforces round 678 D2_Codeforces_源码
打codeforces的神器