Appleman_and_Tree - CheaSim Blog

Appleman_and_Tree

Appleman and Tree

链接

如果觉得我的题解看不懂可以去看 大佬的题解

题目大意

将一颗树节点染成白色或者黑色,减去几条变使得每个联通分支都有一个黑色节点,问有多少种减边方案。


题解

树状dp+dfs

下次看到两种状态加点的。dp应该想到用2维。

  1. 定义$dp[i][j]$表示点$i$在以点$i$为根的子树去掉点$i$所在的联通快有黑点$1$和无黑点$0$的方案数
  2. 假设点$u$,首先如果$u$是黑色,那么$$dp[i][1]=1$$,否则$dp[i][0]=1$。
    1. 点$u$加入一个子树$v$。假设原来$u$没有黑点。
      1. 如果加入的$v$是有黑点的,有两种选择,切断边$u$还是没有黑点,方案数$dp[u][0]=dp[u][0]*dp[v][1]$,不切断边$u$就产生了黑点$dp[u][1]=dp[u][0]*dp[v][1]$
      2. 如果加入的$v$是无黑点的,只能选择不切断。方案数$dp[u][0]=dp[u][0]*dp[v][0]$
    2. 点$$u$$加入一个子树$v$。假设原来$u$有黑点。
      1. 如果加入的$v$是有黑点的,只能选择切断,方案数$dp[u][1]=dp[u][1]*dp[v][1]$
      2. 如果加入的点$v$是无黑点的,只能选择切断,因为不能产生无黑点的联通分支,方案数$dp[u][1]=dp[u][1]*dp[v][0]$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5 + 5;
const ll mod = 1e9 + 7;
struct node{
int to,next;
}G[maxn<<1];
int cnt;
ll dp[maxn][2];
int head[maxn];
void add(int from,int to){
G[cnt].to = to;
G[cnt].next = head[from];
head[from] = cnt++;
}
int n;
void dfs(int u,int fa){
for(int i = head[u];~i;i=G[i].next){
int v = G[i].to;
if(v == fa) continue;
dfs(v,u);
dp[u][1] = dp[u][1]*dp[v][1]%mod + dp[u][0]*dp[v][1]%mod + dp[u][1]*dp[v][0]%mod;
dp[u][1] %= mod;
dp[u][0] = dp[u][0]*dp[v][0]%mod + dp[u][0]*dp[v][1]%mod;
dp[u][0] %= mod;
}
}
int main(){
#ifdef LOCAL
freopen("B.in","r",stdin);
#endif
memset(head,-1,sizeof(head));
scanf("%d",&n);
rep(i,1,n){
int v; scanf("%d",&v);
add(i,v);add(v,i);
}
rep(i,0,n){
scanf("%d",&dp[i][1]);
if(dp[i][1]==0) dp[i][0] = 1;
}
dfs(0,-1);
cout<<dp[0][1]<<endl;
return 0;
}
作者

CheaSim

发布于

2018-08-19

更新于

2018-08-19

许可协议

You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

评论