P3914 染色计数题目描述有一颗N NN个节点的树节点用1 , 2 , ⋯ , N 1,2,\cdots,N1,2,⋯,N编号。你要给它染色使得相邻节点的颜色不同。有M MM种颜色用1 , 2 , ⋯ , M 1,2,\cdots,M1,2,⋯,M编号。每个节点可以染M MM种颜色中的若干种求不同染色方案的数量除以(10 9 7 10^9 71097)的余数。输入格式第1 行2 个整数N , M N,MN,M。接下来N NN行第i ii行表示节点i ii可以染的颜色。第1个整数k i k_iki​表示可以染的颜色数量。接下来k i k_iki​个整数表示可以染的颜色编号。最后N − 1 N - 1N−1行每行2个整数A i , B i A_i,B_iAi​,Bi​表示边( A i , B i ) (A_i,B_i)(Ai​,Bi​)。输出格式1 个整数表示所有的数。输入输出样例 #1输入 #12 2 1 1 2 1 2 1 2输出 #11说明/提示• 对于30% 的数据1 ≤ N ≤ 10 ; 1 ≤ M ≤ 4 1 \le N \le 10; 1 \le M \le 41≤N≤10;1≤M≤4• 对于60% 的数据1 ≤ N ≤ 200 ; 1 ≤ M ≤ 200 1 \le N \le 200; 1 \le M \le 2001≤N≤200;1≤M≤200• 对于100% 的数据1 ≤ N ≤ 5000 ; 1 ≤ M ≤ 5000 1 \le N \le 5000; 1 \le M \le 50001≤N≤5000;1≤M≤5000。C实现#includeiostream#includecstdio#includevectorusingnamespacestd;constintmod1e97;constintN5001;intn,m,f[N][N],dp[N];vectorinta[N];voiddfs(intx,intfa){intlena[x].size();for(inti0;ilen;i){if(a[x][i]fa)continue;dfs(a[x][i],x);for(intj1;jm;j)f[x][j](1ll*f[x][j]*(dp[a[x][i]]-f[a[x][i]][j])%modmod)%mod;}for(inti1;im;i)dp[x]f[x][i],dp[x]%mod;}intmain(){scanf(%d%d,n,m);for(inti1;in;i){intk;scanf(%d,k);for(intj1;jk;j){intx;scanf(%d,x);f[i][x]1;}}for(inti1;in;i){intx,y;scanf(%d%d,x,y);a[x].push_back(y);a[y].push_back(x);}dfs(1,0);printf(%d,dp[1]);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容