正题
题目链接:https://www.luogu.org/problemnew/show/P3914
题目大意
n
n
n个点每个点有些可以染的颜色，要求相邻颜色不相同，方案总数。
解题思路
树形
d
p
dp
dp，定义
f
x
,
i
f_{x,i}
fx,i表示点
x
x
x的染颜色
i
i
i的方案数。然后定义
z
x
=
∑
i
=
1
m
f
x
i
z_x=\sum_{i=1}^mf_{x_i}
zx=∑i=1mfxi
然后显然动态转移方程
f
x
,
i
=
z
y
−
f
y
,
i
(
x
−
>
y
)
f_{x,i}=z_y-f_{y,i}(x->y)
fx,i=zy−fy,i(x−>y)
c
o
d
e
code
code
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std
;
const int XJQ
=1e9+7,N
=5001;
int tot
,n
,m
,f
[N
][N
],z
[N
],ls
[N
];
struct node
{
int to
,next
;
}a
[2*N
];
void addl(int x
,int y
)
{
a
[++tot
].to
=y
;
a
[tot
].next
=ls
[x
];
ls
[x
]=tot
;
}
void dp(int x
,int fa
)
{
for(int i
=ls
[x
];i
;i
=a
[i
].next
)
{
int y
=a
[i
].to
;
if(y
==fa
) continue;
dp(y
,x
);
int k
=1;
for(int j
=1;j
<=m
;j
++)
f
[x
][j
]=1ll*f
[x
][j
]*((z
[y
]-f
[y
][j
]+XJQ
)%XJQ
)%XJQ
;
}
for(int j
=1;j
<=m
;j
++)
(z
[x
]+=f
[x
][j
])%=XJQ
;
}
int main()
{
scanf("%d%d",&n
,&m
);
for(int i
=1;i
<=n
;i
++){
int k
,x
;scanf("%d",&k
);
for(int j
=1;j
<=k
;j
++)
scanf("%d",&x
),f
[i
][x
]=1;
}
for(int i
=1;i
<n
;i
++){
int x
,y
;scanf("%d%d",&x
,&y
);
addl(x
,y
);addl(y
,x
);
}
dp(1,0);
printf("%d",z
[1]);
}
