526互联

Coloring Tree (牛客多校) (BFS序列妙用+ f(n)-f(n+1)+ 组合数学)

发布时间 2023-06-28 13:02:49作者: VxiaohuanV

题目大意:

  • 给一个树, 然后 有k 种颜色可以给树上色
  • 权值是 2个相同颜色节点的最短距离
  • 问 让权值为 D 的方案数

 

题解:

  • 首先 要让2个节点为D, 怎么处理呢? 利用 f(D)- f(D+1) 即可
  • 因为问的是 2个相同颜色点的最短距离, 因此直接bfs用一个bfs序列
  • 然后在bfs一下, 因为之前col的颜色点一定是不同颜色, ans*=K-cnt