首页 > 代码库 > Codeforces Round #263 (Div. 1)
Codeforces Round #263 (Div. 1)
B 树形dp
组合的思想。
Z队长的思路。
dp[i][1]表示以i为跟结点的子树向上贡献1个的方案，dp[i][0]表示以i为跟结点的子树向上贡献0个的方案.
如果当前为叶子节点，dp[i][0] = 1，（颜色为1，可以断开与父节点的连接，颜色为0，不断开，方案恒为1），dp[i][1] = co[i]（i节点的颜色）。
非叶子节点：将所有孩子节点的dp[child][0]乘起来为sum，孩子贡献为0的总方案。
当前颜色为0时， dp[i][1] += sum/dp[child][0]*dp[child][1],（选当前孩子贡献的1） ，
dp[i][0] = sum+dp[i][1](将i与其父亲断开)。
当颜色为1时， dp[i][1] （需儿子们贡献为0）= dp[i][0](需与父亲断开) = sum.
中间除法取模需要用到逆元。 (s/y)%mod = (s*y^mod-2)%mod;
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<vector> 7 #include<cmath> 8 #include<queue> 9 #include<set>10 using namespace std;11 #define N 10001012 #define LL long long13 #define INF 0xfffffff14 #define mod 100000000715 const double eps = 1e-8;16 const double pi = acos(-1.0);17 const double inf = ~0u>>2;18 vector<int>ch[N];19 int dp[N][2];20 int co[N];21 LL q_mod(LL a,LL b)22 {23 LL d,t;24 d = 1,t=a;25 while(b)26 {27 if(b&1) d = (d*t)%mod;28 b/=2;29 t = (t*t)%mod;30 }31 return d;32 }33 LL cal(LL s,LL y,LL x)34 {35 s = (s*x)%mod;36 return (s*q_mod(y,mod-2))%mod;37 }38 void dfs(int u,int pre)39 {40 int i;41 LL s0=1;42 int flag = 0;43 for(i = 0 ; i < ch[u].size() ;i++)44 {45 int v = ch[u][i];46 if(v==pre) continue;47 flag = 1;48 dfs(v,u);49 s0 = (s0*dp[v][0])%mod;50 }51 if(!flag)52 {53 dp[u][0] = 1;54 dp[u][1] = co[u];55 return ;56 }57 if(co[u]==0)58 {59 dp[u][0] = s0;60 dp[u][1] = 0;61 for(i = 0 ;i < ch[u].size() ; i++)62 {63 int v = ch[u][i];64 if(v==pre) continue;65 if(!dp[v][1]) continue;66 dp[u][1] = (dp[u][1]+cal(s0,dp[v][0],dp[v][1]))%mod;67 }68 dp[u][0] = (dp[u][0]+dp[u][1])%mod;69 }70 else71 {72 dp[u][0] = s0;73 dp[u][1] = s0;74 }75 }76 int main()77 {78 int n,i;79 cin>>n;80 for(i = 0 ; i < n-1; i++)81 {82 int u;83 scanf("%d",&u);84 ch[u].push_back(i+1);85 ch[i+1].push_back(u);86 }87 for(i = 0 ; i < n; i++)88 scanf("%d",&co[i]);89 dfs(0,-1);90 cout<<dp[0][1]<<endl;91 return 0;92 }
Codeforces Round #263 (Div. 1)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。