牛客练习赛97：月之暗面 （树上dp dfs）

原题链接：

登录—专业IT笔试面试备考平台_牛客网

题意：

给出一棵 n 个点的树，有 x 种普通颜色，y 种特殊颜色

现在要给树上的每个节点染色，普通颜色染色没有限制，但两个相邻的节点不能染相同颜色的特殊颜色

求染色方案数，答案对 998244353 取模。

解题思路：

一眼树上dp（doge），考虑从叶节点开始往根节点染色，由于有普通，特殊之分，在每个节点额外开一维表示这个节点染哪种类型的颜色。dp【i】【0/1】表示在i这个节点上染普通还是特殊颜色，如果子节点染特殊颜色，那么这个节点染特殊颜色的种数-1就好了。

状态转移方程： 

参考代码：

#includeusing namespace std;#define int long long//不用害怕没开long long#define ll long long#define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);inline int read(){    int x=0,k=1; char c=getchar();    while(c'9'){if(c=='-')k=-1;c=getchar();}    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();    return x*k;}//快读模板const int maxn=2e6+10;const int mod=998244353;int dp[maxn][2],n,x,y;vectorv[maxn];void dfs(int u,int fa){dp[u][0]=1;dp[u][1]=1;//初始设为1,避免乘出0;for(int i=0;i<v[u].size();i++){if(v[u][i]==fa) continue;dfs(v[u][i],u);dp[u][0]=dp[u][0]*(dp[v[u][i]][0]*x%mod+dp[v[u][i]][1]*y%mod)%mod;dp[u][1]=dp[u][1]*(dp[v[u][i]][0]*x%mod+dp[v[u][i]][1]*(y-1)%mod)%mod;//状态转移;}return ;}signed main(){//signed 同 intn=read(),x=read(),y=read();for(int i=1;i<n;i++){int tt=read(),ttt=read();v[tt].push_back(ttt);v[ttt].push_back(tt);//简单建树}dfs(1,0);printf("%lld",(dp[1][0]*x%mod+dp[1][1]*y%mod)%mod);//记得模mod，1e9*1e9会爆long long 啊QwQ}

tips：

菜死了QAQ