小红树上染色时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述小红拿到了一棵树初始所有节点都是白色。小红希望染红若干个节点使得不存在两个白色节点相邻。小红想知道共有多少种不同的染色方案由于答案过大请对10 9 7 10^971097取模。输入描述第一行输入一个正整数n nn代表节点数量。接下来的n − 1 n−1n−1行每行输入两个正整数u , v u,vu,v代表节点u uu和节点v vv有一条边连接。1 ≤ n ≤ 10 5 1≤n≤10^51≤n≤1051 ≤ u , v ≤ n 1≤u,v≤n1≤u,v≤n输出描述一个整数代表染色的方案数。示例1输入2 1 2输出3说明第一个方案只染1 11号节点。第二个方案只染2 22号节点。第三个方案同时染1 11号和2 22号节点。请注意如果每个节点都不染色是不合法的因为这样会导致两个白色节点相邻。解题思路本题核心是树形动态规划求解树上染色的合法方案数约束为不存在两个相邻的白色节点。定义dp[u][0]表示节点u染白色、其子树满足规则的方案数dp[u][1]表示节点u染红色的方案数。状态转移父节点为白时子节点必须全红父节点为红时子节点可白可红。通过深度优先搜索自底向上递推DP值总方案数为根节点两种状态之和减去全白的非法方案后即为答案结果对10 9 7 10^971097取模。算法时间复杂度O ( n ) O(n)O(n)完美适配n ≤ 10 5 n \le 10^5n≤105的大数据规模。总结核心逻辑树形D P DPDP枚举节点染色状态按约束完成状态转移排除全白的非法方案。关键操作D F S DFSDFS遍历树结构递推计算染色方案数总方案减1 11得到合法结果。效率保障线性时间复杂度无冗余计算高效处理大规模树形数据。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e410;constll p1e97;constll INF1e18;constll M2e310;intmain(){ll n;cinn;vvtmp(n1);for(ll i0;in-1;i){ll u,v;cinuv;mp[u].push_back(v);mp[v].push_back(u);}vvtdp(n1,vectorll(2));autodfs[](autodfs,ll u,ll parent)-void{dp[u][0]1;dp[u][1]1;for(autov:mp[u]){if(vparent)continue;dfs(dfs,v,u);dp[u][0](dp[u][0]*dp[v][1])%p;dp[u][1](dp[u][1]*(dp[v][0]dp[v][1]))%p;}};dfs(dfs,1,0);cout(dp[1][0]dp[1][1])%pendl;return0;}