2012-A3-0015
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
题意：一棵树，C种颜色给出若干询问，每次询问是若在树上加一条边，对树上的点进行染色，有边相邻的两点不能同色，问染色方案比原来少了多少。
首先如果是一棵树，第一个点染色有C种，然后之后每个点染色都有C-1种方案，共有C*(C-1)^n-1^种方案
如果加了一条边，那么树可以分解为，一个环，和若干个从环上的点为根的子树。
环上的点的染色方案确定了，剩下的每个与之相连的点从根到叶的顺序就都有C-1种染色方案，共有F,,m,,*(C-1)^n-m^种染色方案，
F,,m,,是m元环C染色，相邻的两点不能同色的染色方案数，
F,,1,,=C, F,,2,,=C*(C-1), F,,3,,=C*(C-1)*(C-2),
那么对大于3的情况呢?我们观察m元环上的某个点，如果把它拿走，考虑剩下的
原来与之相邻的的两个点若颜色不同，那么就是个m-1元环，有F,,m-1,,种染色方案，拿走的那个点就有C-2种染色方案。
原来与之相邻的的两个点若颜色相同，那么就再拿走其中一个，剩下一个m-2元环，有F,,m-2,,种染色方案，而拿走的那个有C-1种染色方案。
于是就可以得出F,,m,, = (C-2)*F,,m-1,,+(C-1)*F,,m-2,,
剩下的就只是求加上边后形成的环的大小了，树上两点的距离+1就是环的大小，树上的距离可以通过求LCA来计算。
{{{
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<vector>
typedef unsigned u32;
typedef unsigned long long ull;
u32 f[51200],pr[51200],nx[102400],eg[102400],hi[51200],ans[102400],fuu[51200],anc[51200];
std::vector<std::pair<u32,u32> > qr[51200];
bool tvis[51200];
void dfs(u32 u,u32 f){
hi[u]=hi[f]+1;
for(u32 p=pr[u];p;p=nx[p])
if(eg[p]!=f)dfs(eg[p],u);
}
u32 uff(u32 x){return x!=fuu[x]?fuu[x]=uff(fuu[x]):x;}
void tarjan(u32 u,u32 f){
for(u32 p=pr[u],v;p;p=nx[p])
if((v=eg[p])!=f){
tarjan(v,u);
fuu[uff(u)]=uff(v);
anc[uff(u)]=u;
}
tvis[u]=1;
for(__typeof(qr[0].end()) it=qr[u].begin();it!=qr[u].end();++it)
if(tvis[it->first])//LCA =uff(u)
ans[it->second]= hi[u]+hi[it->first]-hi[anc[uff(it->first)]]*2;
}
int main(){
srand(time(NULL));
for(u32 n,q,c,p;~scanf("%u%u%u%u",&n,&q,&c,&p);){
{ull pw=1,c1=c-1,c2=c-2;
f[3]=(f[2]=(f[1]=c%p)*c1%p)*c2%p;
for(u32 i=4;i<=n;++i)
f[i]=(f[i-1]*c2+f[i-2]*c1)%p;
for(u32 i=n;--i;f[i]=f[i]*pw%p)
pw=pw*c1%p;}
for(u32 i=1,t=f[1];i<=n;++i){
pr[i]=0;qr[i].clear();tvis[i]=false;fuu[i]=i;
f[i]=(t>=f[i]?t-f[i]:t+p-f[i]);
}
for(u32 i=n,a,b,m=0;--i;){
scanf("%u%u",&a,&b);
eg[++m]=b;nx[m]=pr[a];pr[a]=m;
eg[++m]=a;nx[m]=pr[b];pr[b]=m;
}
u32 rt=rand()%n+1;hi[0]=0;
dfs(rt,0);
for(u32 i=0,a,b;i<q;++i){
scanf("%u %u",&a,&b);
qr[a].push_back(std::make_pair(b,i));
qr[b].push_back(std::make_pair(a,i));
}
tarjan(rt,0);
for(u32 i=0;i<q;++i)
printf("%u\n",f[ans[i]+1]);
}
}
}}}题意：一棵树，C种颜色给出若干询问，每次询问是若在树上加一条边，对树上的点进行染色，有边相邻的两点不能同色，问染色方案比原来少了多少。
首先如果是一棵树，第一个点染色有C种，然后之后每个点染色都有C-1种方案，共有C*(C-1)n-1种方案
如果加了一条边，那么树可以分解为，一个环，和若干个从环上的点为根的子树。
环上的点的染色方案确定了，剩下的每个与之相连的点从根到叶的顺序就都有C-1种染色方案，共有Fm*(C-1)n-m种染色方案，
Fm是m元环C染色，相邻的两点不能同色的染色方案数，
F1=C, F2=C*(C-1), F3=C*(C-1)*(C-2),
那么对大于3的情况呢?我们观察m元环上的某个点，如果把它拿走，考虑剩下的
原来与之相邻的的两个点若颜色不同，那么就是个m-1元环，有Fm-1种染色方案，拿走的那个点就有C-2种染色方案。
原来与之相邻的的两个点若颜色相同，那么就再拿走其中一个，剩下一个m-2元环，有Fm-2种染色方案，而拿走的那个有C-1种染色方案。
于是就可以得出Fm = (C-2)*Fm-1+(C-1)*Fm-2
剩下的就只是求加上边后形成的环的大小了，树上两点的距离+1就是环的大小，树上的距离可以通过求LCA来计算。
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<vector>
typedef unsigned u32;
typedef unsigned long long ull;
u32 f[51200],pr[51200],nx[102400],eg[102400],hi[51200],ans[102400],fuu[51200],anc[51200];
std::vector<std::pair<u32,u32> > qr[51200];
bool tvis[51200];
void dfs(u32 u,u32 f){
hi[u]=hi[f]+1;
for(u32 p=pr[u];p;p=nx[p])
if(eg[p]!=f)dfs(eg[p],u);
}
u32 uff(u32 x){return x!=fuu[x]?fuu[x]=uff(fuu[x]):x;}
void tarjan(u32 u,u32 f){
for(u32 p=pr[u],v;p;p=nx[p])
if((v=eg[p])!=f){
tarjan(v,u);
fuu[uff(u)]=uff(v);
anc[uff(u)]=u;
}
tvis[u]=1;
for(__typeof(qr[0].end()) it=qr[u].begin();it!=qr[u].end();++it)
if(tvis[it->first])//LCA =uff(u)
ans[it->second]= hi[u]+hi[it->first]-hi[anc[uff(it->first)]]*2;
}
int main(){
srand(time(NULL));
for(u32 n,q,c,p;~scanf("%u%u%u%u",&n,&q,&c,&p);){
{ull pw=1,c1=c-1,c2=c-2;
f[3]=(f[2]=(f[1]=c%p)*c1%p)*c2%p;
for(u32 i=4;i<=n;++i)
f[i]=(f[i-1]*c2+f[i-2]*c1)%p;
for(u32 i=n;--i;f[i]=f[i]*pw%p)
pw=pw*c1%p;}
for(u32 i=1,t=f[1];i<=n;++i){
pr[i]=0;qr[i].clear();tvis[i]=false;fuu[i]=i;
f[i]=(t>=f[i]?t-f[i]:t+p-f[i]);
}
for(u32 i=n,a,b,m=0;--i;){
scanf("%u%u",&a,&b);
eg[++m]=b;nx[m]=pr[a];pr[a]=m;
eg[++m]=a;nx[m]=pr[b];pr[b]=m;
}
u32 rt=rand()%n+1;hi[0]=0;
dfs(rt,0);
for(u32 i=0,a,b;i<q;++i){
scanf("%u %u",&a,&b);
qr[a].push_back(std::make_pair(b,i));
qr[b].push_back(std::make_pair(a,i));
}
tarjan(rt,0);
for(u32 i=0;i<q;++i)
printf("%u\n",f[ans[i]+1]);
}
}