zrj2012-B3-0015

从 Trac 迁移的文章

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

原文章内容如下：

题目大意：一开始有一棵树，你有C中颜色去给每个节点染色，但是有边相连的节点不能有相同的颜色。现在给M个询问，如果把某两个点之间再连一条边，会有少多少种方案。
考虑连边后图的结构，可以发现是一个环，然后环上每个点可能带有一些子树。如果我们确定了环的染色方案，我们发现那些子树的染色方案数必然是(c-1)^(n-k)^(其中k为环上点数).而环的染色方案数只于k有关，因此先做两个预处理，然后就是查询环的长度了，这个问题就转为求树上两点的lca。求lca的一个比较常见的方法是记录每个点第2^k^个祖先是谁，然后每次把两个点调整到相同高度，往上查询。

题目大意：一开始有一棵树，你有C中颜色去给每个节点染色，但是有边相连的节点不能有相同的颜色。现在给M个询问，如果把某两个点之间再连一条边，会有少多少种方案。

考虑连边后图的结构，可以发现是一个环，然后环上每个点可能带有一些子树。如果我们确定了环的染色方案，我们发现那些子树的染色方案数必然是(c-1)^(n-k)(其中k为环上点数).而环的染色方案数只于k有关，因此先做两个预处理，然后就是查询环的长度了，这个问题就转为求树上两点的lca。求lca的一个比较常见的方法是记录每个点第2^k个祖先是谁，然后每次把两个点调整到相同高度，往上查询。