小红树上染色【牛客tracker 每日一题】
小红树上染色
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
小红拿到了一棵树，初始所有节点都是白色。
小红希望染红若干个节点，使得不存在两个白色节点相邻。
小红想知道，共有多少种不同的染色方案？
由于答案过大，请对10 9 + 7 10^9+7109+7取模。
输入描述：
第一行输入一个正整数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≤105
1 ≤ 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^9+7109+7取模。算法时间复杂度O ( n ) O(n)O(n)，完美适配n ≤ 10 5 n \le 10^5n≤105的大数据规模。
总结
核心逻辑：树形D P DPDP枚举节点染色状态，按约束完成状态转移，排除全白的非法方案。
关键操作：D F S DFSDFS遍历树结构，递推计算染色方案数，总方案减1 11得到合法结果。
效率保障：线性时间复杂度，无冗余计算，高效处理大规模树形数据。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e4+10;constll p=1e9+7;constll INF=1e18;constll M=2e3+10;intmain(){ll n;cin>>n;vvtmp(n+1);for(ll i=0;i<n-1;i++){ll u,v;cin>>u>>v;mp[u].push_back(v);mp[v].push_back(u);}vvtdp(n+1,vector<ll>(2));autodfs=[&](autodfs,ll u,ll parent)->void{dp[u][0]=1;dp[u][1]=1;for(autov:mp[u]){if(v==parent)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])%p<<endl;return0;}