team2012-B2-sol-0015

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意：给出一棵树，使用c种颜色染色，要求有边直接相连的颜色不同。现在有q次询问，每次询问为加1条边，问染色方案减少了多少种。
思路：通过最近公共祖先求出加上边所构成的环的大小（假设为L），则加上后的方案数为环上的方案数*(c-1)^(n-L)

题意：给出一棵树，使用c种颜色染色，要求有边直接相连的颜色不同。现在有q次询问，每次询问为加1条边，问染色方案减少了多少种。

思路：通过最近公共祖先求出加上边所构成的环的大小（假设为L），则加上后的方案数为环上的方案数*(c-1)^(n-L)