AT4537 题解

AT4537:Independent Set

Description

给定一棵含有 $n~(1 \leq n \leq 10^5)$ 个节点树,每一个节点可以染成黑色或白色,其中任意两个相邻的节点不能同时为黑色,求染色的方案数,结果对 $10^9+7$ 取模。

Solution

首先我们可以想到这是树形 DP,考虑如何转移。

统计总方案数需要用到一个乘法原理

我们先考虑没有任意两个相邻的节点不能同时为黑色这个条件的情况。

假设当前节点 $t_i$ 有 $4$ 个儿子,每个儿子的方案数分别为 $3~5~1~2$,加上本节点可以涂成黑色和白色两种情况,那么当前结点的方案数即为 $3 \times 5 \times 1 \times 2 \times 2=60$。

我们设 $dp_i$ 为节点 $t_i$ 的方案数,那么其转移方程为:
$$
dp_i=2 \times \prod_{t_j 为 t_i 的子节点}dp_j
$$
现在我们来考虑加上任意两个相邻的节点不能同时为黑色这个条件的情况。

设 $dp_{i,0/1}$ 表示节点 $t_i$ 填白 / 黑色的方案数,那么 $dp_{i,0}$ 可以由它的子节点们 $dp_{j,0/1}$ 转移而来,而 $dp_{i,1}$ 只能由 $dp_{j,0}$ 转移。

由此我们得出方程:
$$
\begin{aligned}
dp_{i,0}&=\prod_{t_j 为 t_i 的子节点}\left(dp_{j,0}+dp_{j,1}\right)\\
dp_{i,1}&=\prod_{t_j 为 t_i 的子节点}dp_{j,0}
\end{aligned}
$$
那么就是一个基础的树形 DP 转移。

Code
/*
    Author: Ruakker
    Date: 2021-05-16 20:32:00
    LastEditTime: 2021-05-16 21:41:32
*/
#include<cstdio>
#include<cctype>
#include<cstring>
#define ll long long
#define inf 0x3f3f3f3f
#define int long long
const int BUFSIZE=(1<<21)+1;static char ibuf[BUFSIZE],*i1=ibuf,*i2=ibuf,obuf[BUFSIZE],*o1=obuf,*o2=o1+BUFSIZE-1;inline void flush(){fwrite(obuf,1,o1-obuf,stdout),o1=obuf;}
#define getchar()i1==i2&&(i2=(i1=ibuf)+fread(ibuf,1,BUFSIZE,stdin),i1==i2)?EOF:*i1++
#define putchar(x)*o1++=x,(o1==o2)?flush():void()
struct flusher{~flusher(){flush();}}io;template<typename Val>inline Val read(){Val res=0,w=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')w=-1;for(;isdigit(ch);ch=getchar())res=(res<<3)+(res<<1)+(ch^48);return res*w;}template<typename Val>void write(Val num){if(num<0)num=-num,putchar('-');if(num>9)write(num/10);putchar(num%10+'0');}template<typename Val>inline void writeln(Val num){write<Val>(num),putchar('\n');}inline void readstr(char*s){char ch=getchar();int cnt=0;for(;!isgraph(ch);ch=getchar());for(;isgraph(ch);ch=getchar())s[cnt++]=ch;s[cnt]=0;}inline void writestr(char*s){int len=strlen(s);for(int i=0;i<len;++i)putchar(s[i]);}
/* 以上为压行过的 IO 板子,可以忽略 */
const int N=1e5+5,P=1e9+7;
struct Ruakker{
    int nxt,to;
}e[N<<1];
int n,head[N],tote=1,indgr[N],dp[N][2];
inline void adde(int x,int y){e[++tote].to=y,e[tote].nxt=head[x],head[x]=tote;}
void dfs(int u,int pre){
    dp[u][0]=dp[u][1]=1;
    for (int i=head[u];i;i=e[i].nxt){
        int v=e[i].to;
        if (v==pre) continue;
        dfs(v,u);
        (dp[u][0]*=dp[v][0]+dp[v][1])%=P;
        (dp[u][1]*=dp[v][0])%=P;
    }
}
signed main(){
    n=read<int>();
    for (int i=1;i<n;++i){
        int u=read<int>(),v=read<int>();
        adde(u,v),adde(v,u);
    }
    dfs(1,-1);
    writeln<int>((dp[1][0]+dp[1][1])%P);
    // for (int i=1;i<=n;++i)
    //  write<int>(dp[i][0]),putchar(' '),writeln<int>(dp[i][1]);
    return 0;
}
     Title: AT4537 题解
       Url: https://blog.ruakker.cn/index.php/solution-at4537/
Author: Ruakker
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇