首页 > 其他分享 >CF-461-B-树形DP

CF-461-B-树形DP

时间:2024-01-22 12:11:07浏览次数:38  
标签:连通 黑色 int 461 CF DP 节点 dp mod

461-B 题目大意

给定一棵\(n\)个节点的树,节点编号从\(0\)开始,每个节点要么为白色要么为黑色,你需要删除一些边,使得剩下的各个连通块中有且仅有一个黑色节点。

问有多少种删边方案数,答案对\(10^9+1\)取模。


Solution

考虑树形DP,令\(dp[x][0/1]\)表示节点\(x\)属于无黑色节点/有黑色节点的连通块的方案数,节点\(y\)是\(x\)的儿子节点,初始化\(dp[x][col[x]]=1\)。

对于\(dp[x][1]\),有三种情况:

  • \(x\)属于有黑色节点的连通块,\(y\)属于有黑色节点的连通块,删去两点之间的边。
  • \(x\)属于有黑色节点的连通块,\(y\)属于没有黑色节点的连通块,无需删边。
  • \(x\)属于没有黑色节点的连通块,\(y\)属于有黑色节点的连通块,无需删边。

对于\(dp[x][0]\),有两种情况:

  • \(x\)属于没有黑色节点的连通块,\(y\)属于有黑色节点的连通块,删去两点之间的边。
  • \(x\)属于没有黑色节点的连通块,\(y\)属于没有有黑色节点的连通块,无需删边。

那么转移方程如下:

\[dp[x][1]=dp[x][1]*dp[y][0]+dp[x][1]*dp[y][1]+dp[x][0]*dp[y][1] \]

\[dp[x][0]=dp[x][0]*dp[y][0]+dp[x][0]*dp[y][1] \]

要注意的是\(dp[x][1]\)的转移受\(dp[x][0]\)的影响,所以要先进行前者的转移,时间复杂度\(O(n)\)。

#include<bits/stdc++.h>
using namespace std;
using ll=long long;

const int mod=1e9+7;

void solve(){
    int n;
    cin>>n;
    vector<vector<int>> e(n);
    for(int i=1;i<n;i++){
        int x;
        cin>>x;
        e[x].push_back(i);
    }
    vector<array<ll,2>> dp(n);
    for(int i=0;i<n;i++){
        int col;
        cin>>col;
        dp[i][col]=1;
    }
    function<void(int)> dfs=[&](int x){
        for(auto y:e[x]){
            dfs(y);
            dp[x][1]=((dp[x][1]*dp[y][1]%mod)+(dp[x][1]*dp[y][0]%mod)+(dp[x][0]*dp[y][1]%mod))%mod;
            dp[x][0]=((dp[x][0]*dp[y][1]%mod)+(dp[x][0]*dp[y][0]%mod))%mod;
        }
    };
    dfs(0);
    cout<<dp[0][1];
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}

标签:连通,黑色,int,461,CF,DP,节点,dp,mod
From: https://www.cnblogs.com/fengxue-K/p/17979774

相关文章

  • CF1920E 题解
    CF1920E被这种题卡了,脸都不要了。仔细读题,发现序列可以分成两部分(\(0\)和\(1\))来考虑。在合法序列中,对于一个\(1\),它产生的子串贡献一定是(假设与上一个\(1\)之间有\(x\)个\(0\),与下一个\(1\)之间有\(y\)个\(0\)):\[(x+1)(y+1)\]如果去DP这\(n\)个\(1\),易得转......
  • CF455D Serega and Fun 题解
    题目链接:CF或者洛谷本题是可以用平衡树去做的,具体的为每个\(k\)开一棵平衡树去维护相对位置,而这种移动操作用平衡树维护又是很容易做到的,这种做法是双\(log\)。在\(1e5\)的数据下,我们来说说好写的分块该如何去写。黑色的代表一个块,考虑暴力修改情况,假如原来的数字为\([1......
  • CF-570-D-启发式合并
    570-D题目大意给定一棵\(n\)个节点的树,根节点为\(1\),每个节点上有一个小写字母\(ch\)。定义节点\(x\)的深度为\(x\)到根节点的路径上的节点数量。\(q\)次询问,每次询问查询以\(x\)为根的子树之中所有深度为\(d\)的节点上字母重排之后是否可以构成一个回文串。Solution对于一组......
  • 从CF1901C学习除二向下取整的思路
    https://codeforces.com/problemset/problem/1901/C我发现对于向下取整向上取整的题目(特指除二),没有一些常见的思路积累。Description给定一个长度为\(n\)的序列\(\{a_n\}\)。每次操作你需要选择一个整数\(x\)并将所有\(a_i\)替换为\(\lfloor\frac{a_i+x}2\rfloo......
  • CF1375B Neighbor Grid 题解
    题意简述给你一个$n$行$m$列的矩阵,要求你让这个矩阵是“完美”的。“完美”的定义如下:若当前的格子里是一个正整数$k$,那么与这个网格相邻(有公共边)的$k$个格子也必须有一个正整数。若当前的格子里是$0$,那么不受上述的限制。你可以对任意的一个格子加上$1$,次数......
  • 对CF1904C的代码优化
    https://www.luogu.com.cn/problem/CF1904C分讨,然后\(k=2\)的时候肯定要写暴力,但是我的暴力很不优雅。石山voidsolve(){intn,k;cin>>n>>k;vector<ll>a(n+1);for(inti=1;i<=n;i++)cin>>a[i];if(k>=3){......
  • CF-915-F-并查集
    915-F题目大意给定一棵\(n\)个节点的树,节点带权,设函数\(I(x,y)\)等于点\(x\)到点\(y\)的路径上最大的点权与最小的点权之差。求:\[\sum_{i=1}^{n}\sum_{j=i}^{n}I(i,j)\]Solution令函数\(F(i,j)\)等于点\(x\)到点\(y\)的路径上最大的点权,函数\(G(i,j)\)等于点\(x\)到点\(y\)......
  • HDP 相关日志位置
      1.HIVESERVER2的日志:/var/log/hive-rwxrwxrwx1hivehadoop4791月1418:20hive.err-rwxrwxrwx1hivehadoop24381月1320:27hivemetastore-gc-2024-01-13_20-27-25.log.0.current-rwxrwxrwx1hivehadoop1032641月1321:47hivemetastor......
  • 数位 dp
    前言带有私人情感,请理性阅读。直接跳到理论去算了。前言不同于其他dp,数位dp的初学者很容易懵逼,比如我。都是递推版数位dp害的!看到oj上“简单”的模板题,题解中生动抽象的分析——什么顶着上界枚举、分开讨论、处理前导\(0\)、满\(i\)位时记为\(dp_i\)、统计答案......
  • 线性DP简单总结
    线性DP简单总结动态规划原理可以用动态规划解决的问题,应具备三种条件:最优子结构(由小推大)无后效性(由过去推现在)子问题重叠(已经求解的子问题不必重复求解)动态规划构成“状态”“阶段”“决策”为动态规划三要素。最长上升子序列问题给定一个长度为\(n\)的序列\(A......