核心内容摘要
美国XXXXXL56Endian的起源
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
的余数。
输入格式第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,