team2012-E1-mysol-0015
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
/* 解题报告 //
给出一棵树，给每个结点染色，要求相邻两结点不能同色，共有 C 种颜色可选
并且有一些询问，每次询问若在 X 和 Y 之间加一条边，则染色方案数减少多少
首先，对于原始的树，方案数必定是 C * (C - 1) ^ (N - 1)
选择任意一点为根，它自身可以染 C 种颜色，确定了它的颜色之后
其余结点都不能和父亲同色，从而得到上面的公式
树上加一条边会形成乌贼型图，比如这样：
}}}
{{{
#!html
<div style="font-family: 'ＭＳ Ｐゴシック','モナーフォント','IPAモナーフォント','IPA モナ','M+IPAモナ','Mona','mona-gothic-jisx0208.1990-0','sans-serif'; line-height: normal; white-space: pre-wrap; word-wrap: break-word;"> ＿＿＿＿＿＿__<br> . ´ ＿＿｀丶_<br> ／ ,． ´: : : : : : : : :｀ 、<br> ／ | ／: : : : : : : : : :、: : : : : : : ＼<br> / ｜ .／ : : : : ト､: : : : : ∧: :､ : : : :!⌒<br> / :| /: : : :∧ ,:|--＼ : / ‐∨､＼ : |<br>. / ' /: : : : :|／､| ｀ |: Ｖ<br> ｀ ＝ニニニV : : : : : | ,x=､ Vﾊ<br> { ｜: |: |: : :| ,x==､ 〃 V|<br> '. j : ﾑ:|∨:| 〃 _＿＿_ /// }|<br> ∨: :{ r|: : :l/// r ´ ＼} ハ、<br> /: : : ヽ|: : :| ｜ ﾉ ／: : : :＼<br> ＿／ : : /: :/ : : ト ._丶 ＿＿ . イ: :{ ＼:_:_: :ヽ<br> ／ : : : : :,．一': :_／: :x'⌒＼l|｀ヽ、: : ﾄ､: ヽ |: :｜<br> ┌―一': : :／￣/: : : :／: : ／ }} } ＼ | }: : } |: :└┐<br> |: : : : : : :/＿_,/: : ／| : ／ ,.ｲ{ !＼ ＼ ヽ: ヽ ￣]: :|<br> ／: : : : |￣ |: : :_:_;∧__|f二yｲ |: 〉 V（ ｰ' ）､〉 : 〉 く : : :＼<br> ＼ : : : : > __」: : | 〉: : : （_／:〈 ／ ∨下-:' : :/ ＼／<br>. ＼／ ＼ : : :＼: : : : ∧: ／､ ,ﾊ |: : : : :|<br> ＼／ ￣￣ /〈＼O＼ __＿___ ／O 〉￣￣<br> ￣ ＼＼ __O＿_O／／<br> ／＞ー-----r' |<br> 〈／ し'<br><br></div>
}}}
{{{
哦好像图片用错了，总之是一个环加一些根结点在环上的树，意思理解了就行
于是先预处理出一个数组，表示长度为 x 的环的染色方案数
公式是 F[i] = F[i - 1] * (C - 2) + F[i - 2] * (C - 1) (i >= 4)
前三项略，至于整个公式怎么得出的，分析起来比较麻烦，建议自己推去吧
环上的点染色方案数确定后，剩下 N - x 个点的方案数就是 (C - 1) ^ (N - x)
如何在添加一条边时计算出这个环的大小？LCA（最近公共祖先）
关于 LCA 的做法有很多，不会的话可以去网上搜一下
我的做法是预处理，得到每个结点的父亲，父亲 ^ 2，父亲 ^ 4 ...
同时记录每个结点的高度，在做 LCA 时，分为这么几步：
1. 先将查询的结点 X 和 Y 化归到同一高度
2. 若 X == Y 则说明已经找到了 LCA，返回 X
3. 从大往小检查：如果将它们提升 2 ^ i 的高度，是否是同一个结点
若是同一个结点，则什么也不做
若非同一个结点，则将它们提升 2 ^ i 的高度，到达 X' 和 Y'
4. 最后检查完毕时，他们的直接父亲必定是同一个结点，返回 fa[X]
我觉得这种做法比 tarjan 离线做法简单易懂，如果还有不理解的可以看看代码
// By 猛犸也钻地 @ 2012.07.22 */
}}}
{{{
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
int fa[50001][16],lv[50001],ans[50001];
vector<int> e[50001];
void make_tree(int x, int src){
fa[x][0]=src;
lv[x]=lv[src]+1;
for(int i=1;i<16;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for(size_t i=0;i<e[x].size();i++)
if(e[x][i]!=src) make_tree(e[x][i],x);
}
int gao(int x, int y){
int c=lv[x]-lv[y];
if(c>0) for(int i=0;i<16;i++) if(+c&1<<i) x=fa[x][i];
if(c<0) for(int i=0;i<16;i++) if(-c&1<<i) y=fa[y][i];
c=abs(c);
if(x==y) return c;
for(int i=15;~i;i--) if(fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
c+=2<<i;
}
return c+=2;
}
int main(){
int n,m,c,p;
while(scanf("%d%d%d%d",&n,&m,&c,&p)==4){
int x,y,w=1;
ans[1]=c;
ans[2]=c*LL(c-1)%p;
ans[3]=c*LL(c-1)%p*(c-2)%p;
for(int i=4;i<=n;i++)
ans[i]=(LL(c-2)*ans[i-1]+LL(c-1)*ans[i-2])%p;
for(int i=n;i>=1;i--){
ans[i]=ans[i]*LL(w)%p;
w=w*LL(c-1)%p;
}
for(int i=1;i!=n;i++){
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
make_tree(1,1);
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
printf("%d\n",(ans[1]+p-ans[gao(x,y)+1])%p);
}
for(int i=1;i<=n;i++) e[i].clear();
}
}
}}}/* 解题报告 //
给出一棵树，给每个结点染色，要求相邻两结点不能同色，共有 C 种颜色可选
并且有一些询问，每次询问若在 X 和 Y 之间加一条边，则染色方案数减少多少
首先，对于原始的树，方案数必定是 C * (C - 1) ^ (N - 1)
选择任意一点为根，它自身可以染 C 种颜色，确定了它的颜色之后
其余结点都不能和父亲同色，从而得到上面的公式
树上加一条边会形成乌贼型图，比如这样：
＿＿＿＿＿＿__
. ´ ＿＿｀丶_
／ ,． ´: : : : : : : : :｀ 、
／ | ／: : : : : : : : : :、: : : : : : : ＼
/ ｜ .／ : : : : ト､: : : : : ∧: :､ : : : :!⌒
/ :| /: : : :∧ ,:|--＼ : / ‐∨､＼ : |
. / ' /: : : : :|／､| ｀ |: Ｖ
｀ ＝ニニニV : : : : : | ,x=､ Vﾊ
{ ｜: |: |: : :| ,x==､ 〃 V|
'. j : ﾑ:|∨:| 〃 _＿＿_ /// }|
∨: :{ r|: : :l/// r ´ ＼} ハ、
/: : : ヽ|: : :| ｜ ﾉ ／: : : :＼
＿／ : : /: :/ : : ト ._丶 ＿＿ . イ: :{ ＼:_:_: :ヽ
／ : : : : :,．一': :_／: :x'⌒＼l|｀ヽ、: : ﾄ､: ヽ |: :｜
┌―一': : :／￣/: : : :／: : ／ }} } ＼ | }: : } |: :└┐
|: : : : : : :/＿_,/: : ／| : ／ ,.ｲ{ !＼ ＼ ヽ: ヽ ￣]: :|
／: : : : |￣ |: : :_:_;∧__|f二yｲ |: 〉 V（ ｰ' ）､〉 : 〉 く : : :＼
＼ : : : : > __」: : | 〉: : : （_／:〈 ／ ∨下-:' : :/ ＼／
. ＼／ ＼ : : :＼: : : : ∧: ／､ ,ﾊ |: : : : :|
＼／ ￣￣ /〈＼O＼ __＿___ ／O 〉￣￣
￣ ＼＼ __O＿_O／／
／＞ー-----r' |
〈／ し'
. ´ ＿＿｀丶_
／ ,． ´: : : : : : : : :｀ 、
／ | ／: : : : : : : : : :、: : : : : : : ＼
/ ｜ .／ : : : : ト､: : : : : ∧: :､ : : : :!⌒
/ :| /: : : :∧ ,:|--＼ : / ‐∨､＼ : |
. / ' /: : : : :|／､| ｀ |: Ｖ
｀ ＝ニニニV : : : : : | ,x=､ Vﾊ
{ ｜: |: |: : :| ,x==､ 〃 V|
'. j : ﾑ:|∨:| 〃 _＿＿_ /// }|
∨: :{ r|: : :l/// r ´ ＼} ハ、
/: : : ヽ|: : :| ｜ ﾉ ／: : : :＼
＿／ : : /: :/ : : ト ._丶 ＿＿ . イ: :{ ＼:_:_: :ヽ
／ : : : : :,．一': :_／: :x'⌒＼l|｀ヽ、: : ﾄ､: ヽ |: :｜
┌―一': : :／￣/: : : :／: : ／ }} } ＼ | }: : } |: :└┐
|: : : : : : :/＿_,/: : ／| : ／ ,.ｲ{ !＼ ＼ ヽ: ヽ ￣]: :|
／: : : : |￣ |: : :_:_;∧__|f二yｲ |: 〉 V（ ｰ' ）､〉 : 〉 く : : :＼
＼ : : : : > __」: : | 〉: : : （_／:〈 ／ ∨下-:' : :/ ＼／
. ＼／ ＼ : : :＼: : : : ∧: ／､ ,ﾊ |: : : : :|
＼／ ￣￣ /〈＼O＼ __＿___ ／O 〉￣￣
￣ ＼＼ __O＿_O／／
／＞ー-----r' |
〈／ し'
哦好像图片用错了，总之是一个环加一些根结点在环上的树，意思理解了就行
于是先预处理出一个数组，表示长度为 x 的环的染色方案数
公式是 F[i] = F[i - 1] * (C - 2) + F[i - 2] * (C - 1) (i >= 4)
前三项略，至于整个公式怎么得出的，分析起来比较麻烦，建议自己推去吧
环上的点染色方案数确定后，剩下 N - x 个点的方案数就是 (C - 1) ^ (N - x)
如何在添加一条边时计算出这个环的大小？LCA（最近公共祖先）
关于 LCA 的做法有很多，不会的话可以去网上搜一下
我的做法是预处理，得到每个结点的父亲，父亲 ^ 2，父亲 ^ 4 ...
同时记录每个结点的高度，在做 LCA 时，分为这么几步：
1. 先将查询的结点 X 和 Y 化归到同一高度
2. 若 X == Y 则说明已经找到了 LCA，返回 X
3. 从大往小检查：如果将它们提升 2 ^ i 的高度，是否是同一个结点
若是同一个结点，则什么也不做
若非同一个结点，则将它们提升 2 ^ i 的高度，到达 X' 和 Y'
4. 最后检查完毕时，他们的直接父亲必定是同一个结点，返回 fa[X]
我觉得这种做法比 tarjan 离线做法简单易懂，如果还有不理解的可以看看代码
// By 猛犸也钻地 @ 2012.07.22 */
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
int fa[50001][16],lv[50001],ans[50001];
vector<int> e[50001];
void make_tree(int x, int src){
fa[x][0]=src;
lv[x]=lv[src]+1;
for(int i=1;i<16;i++) fa[x][i]=fa[fa[x][i-1]][i-1];
for(size_t i=0;i<e[x].size();i++)
if(e[x][i]!=src) make_tree(e[x][i],x);
}
int gao(int x, int y){
int c=lv[x]-lv[y];
if(c>0) for(int i=0;i<16;i++) if(+c&1<<i) x=fa[x][i];
if(c<0) for(int i=0;i<16;i++) if(-c&1<<i) y=fa[y][i];
c=abs(c);
if(x==y) return c;
for(int i=15;~i;i--) if(fa[x][i]!=fa[y][i]){
x=fa[x][i];
y=fa[y][i];
c+=2<<i;
}
return c+=2;
}
int main(){
int n,m,c,p;
while(scanf("%d%d%d%d",&n,&m,&c,&p)==4){
int x,y,w=1;
ans[1]=c;
ans[2]=c*LL(c-1)%p;
ans[3]=c*LL(c-1)%p*(c-2)%p;
for(int i=4;i<=n;i++)
ans[i]=(LL(c-2)*ans[i-1]+LL(c-1)*ans[i-2])%p;
for(int i=n;i>=1;i--){
ans[i]=ans[i]*LL(w)%p;
w=w*LL(c-1)%p;
}
for(int i=1;i!=n;i++){
scanf("%d%d",&x,&y);
e[x].push_back(y);
e[y].push_back(x);
}
make_tree(1,1);
for(int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
printf("%d\n",(ans[1]+p-ans[gao(x,y)+1])%p);
}
for(int i=1;i<=n;i++) e[i].clear();
}
}