原题链接：

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

题意：

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

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

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

解题思路：

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

状态转移方程： 

参考代码：

#include<bits/stdc++.h>
using 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<'0'||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;
vector<int>v[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 同 int
	n=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