UOJ Logo Sharp Sword 剑锋 OI

SSOI

剑锋OI#Ⅱ期#秩序团#模拟赛#20180107#003

比赛通知

标题内容时间
A题解题思路解法:树形DP问题。定义: dp[u][0]表示以u为根的子树对父亲的贡献为0 dp[u][1]表示以u为根的子树对父亲的贡献为1 现在假设u为白色,它的子树有x,y,z,那么有 dp[u][1]+=dp[x][1]*dp[y][0]*dp[z][0]+dp[x][0]*dp[y][1]*dp[z][0]+dp[x][0]*dp[y][0]*dp[z][1] dp[u][0]+=dp[x][0]*dp[y][0]*dp[z][0] 然后判断u的颜色,假设u的父亲为p 1.为黑色,不切断边(u,p),那么dp[u][1]=dp[u][0],切断(u,p),那么dp[u][0]不变 2.为白色,如果切断(u,p),dp[u][0]还要加上dp[u][1] 2018-01-08 13:57:10
题目来源Codeforces Round #263 (Div. 1) 461B Codeforces Round #401 (Div. 2) 777A Codeforces Round #401 (Div. 2) 777B Codeforces Round #401 (Div. 2) 777C Codeforces Round #401 (Div. 2) 777D Codeforces Round #401 (Div. 2) 777E2018-01-07 14:40:32

比赛已结束

此次比赛为OI赛制。

注意:比赛时只显示测样例的结果。

报名选手列表