nowcoder.62.C(dp)_牛客博客

$Description$
给定一棵树，求有多少个集合 $S$ ,满足 $\forall x,y \in S ,LCA(x,y) \in S \quad (x!=y)$

$Code$
树形 $dp$ ,设 $dp[1][u]$ 表示 $u$ 选择节点的方法数， $dp[0][u]$ 表示不选择 $u$ 节点的方法数。

对于 $dp[1][u]$ ,显然有 $dp[1][u]=\prod _{v=son_u} (dp[0][v]+dp[1][v])$ 。
对于 $dp[0][u]$ ,首先可以选择空集也就是 $dp[0][u]=1$ , 然后不同子树不能同时选择
而且每颗子树都会有空的情况，所以还要减去每颗子树空的情况。 $dp[0][u]=1+\sum_{v=son_u} (dp[0][v]+dp[1][v]-1)$

#include<bits/stdc++.h>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
#define sc scanf
#define pr printf
#define IN freopen("in.txt","r",stdin);
#define OUT freopen("out.txt","w",stdout);
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+6;
const int mod=1e9+7;
int O(){putchar('\n');return 0;}template<typename T,typename... Ty>
int O(const T& a,const Ty&... b){cout<<a<<' ';return O(b...);}
void I(){}template<typename T,typename... Ty>void I(T& a,Ty&... b){cin>>a;I(b...);}
template<typename T>void db(T *bg,T *ed){while(bg!=ed)cout<<*bg++<<' ';pr("\n");}
inline ll mul_64(ll x,ll y,ll c){return (x*y-(ll)((long double)x/c*y)*c+c)%c;}
inline ll ksm(ll a,ll b,ll c){ll ans=1;for(;b;b>>=1,a=a*a%c)if(b&1)ans=ans*a%c;return ans;}
struct node{
    int v,next;
}g[N<<1|1];
int cnt=0,head[N];
int n;
void add(int u,int v){
    g[++cnt]={v,head[u]};
    head[u]=cnt;
}
ll dp[2][N];
void dfs(int u,int fa){
    dp[0][u]=dp[1][u]=1;
    for(int i=head[u];~i;i=g[i].next){
        int v=g[i].v;
        if(v==fa)continue;
        dfs(v,u);
        dp[1][u]=dp[1][u]*(dp[0][v]+dp[1][v])%mod;
        dp[0][u]=(dp[0][u]+dp[0][v]+dp[1][v]-1)%mod;
    }
}
int main(){
    me(head,-1);
    I(n);
    for(int i=1;i<n;i++){
        int u,v;
        sc("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    dfs(1,0);
    O((dp[1][1]+dp[0][1])%mod);
}