题解 | #小红树上染色#
小红树上染色
https://www.nowcoder.com/practice/e89ce3d055024e3c996b629f8286c1fc
树形DP分两种状态，当前点不染红则孩子必须染红，当前点染红则孩子可红可白，最后把根节点两种状态相加取模即可。
void solve(){
int n;cin>>n;
vvi c(n+1);
for(int i=1;i<n;++i){
int u,v;cin>>u>>v;
c[u].push_back(v);
c[v].push_back(u);
}
vi a(n+1),b,t;
b.reserve(n);
t.push_back(1);
a[1]=-1;
while(!t.empty()){
int u=t.back();
t.pop_back();
b.push_back(u);
for(int v:c[u]){
if(v==a[u])continue;
a[v]=u;
t.push_back(v);
}
}
vll x(n+1,1),y(n+1,1);
for(int i=(int)b.size()-1;i>=0;--i){
int u=b[i];
x[u]=1;
y[u]=1;
for(int v:c[u]){
if(v==a[u])continue;
x[u]=x[u]*y[v]%MOD;
y[u]=y[u]*(x[v]+y[v])%MOD;
}
}
cout<<(x[1]+y[1])%MOD<<endl;
}
查看12道真题和解析
