prow2012-A3-0015
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
题意：一棵树，C种颜色给出若干询问，每次询问是若在树上加一条边，对树上的点进行染色，有边相邻的两点不能同色，问染色方案比原来少了多少。
首先知道一棵点数为N的树染色方案数是C*(C-1)^(N-1)^，如果连边的话，变成一个环作为root的树，这时总方案数就是环的染色方案*(C-1)^(left_nodes)
现在问题是快速求得连边后的环中顶点个数，用LCA可以离线求得。
{{{
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
int node[400000],next[400000],edge[100000],tot;
int father[100000],ans[100000];
bool lcavis[100000],visit[100000];
void insert(int a,int b){
node[tot] = b,next[tot]=edge[a],edge[a] = tot++;
}
int depth[50000];
#define PII pair<int,int>
vector<PII> Q[50000];
void init(int N){
for (int i=0;i<N;i++)
father[i] = i,Q[i].clear(),edge[i] = -1,lcavis[i] = visit[i] = false;
}
int findroot(int x){
if (father[x]==x) return x;
else return father[x] = findroot(father[x]);
}
void Unoin(int a,int b){
int fa = findroot(a);
int fb = findroot(b);
father[fa] = fb;
}
void calc(int v){
int t = Q[v].size();
for (int i=0;i<t;i++)
{
int u = Q[v][i].first;
if (!visit[u]) continue;
ans[Q[v][i].second] = depth[u]+depth[v]-2*depth[findroot(u)];
}
}
void LCA(int v){
lcavis[v] = true;
for (int i=edge[v];i!=-1;i=next[i]){
if (!lcavis[node[i]]){
LCA(node[i]);
Unoin(node[i],v);
}
}
visit[v] = true;
calc(v);
}
void dfs(int now,int fa){
if (fa==-1) depth[now] = 0;
else
depth[now] = depth[fa]+1;
for (int i=edge[now];i!=-1;i=next[i])
if (node[i]!=fa)
dfs(node[i],now);
}
long long mul(int n,int m,int P){
long long ans = 1,r = n;
while(m){
if (m&1) ans*=r,ans%=P;
r*=r;
r%=P;
m>>=1;
}
return ans;
}
int N,M,C,P;
long long f[60000];
int main(){
int i,a,b;
while(scanf("%d%d%d%d",&N,&M,&C,&P)!=EOF){
f[1] = 1LL*C%P,f[2] = 1LL*C*(C-1)%P,f[3] = f[2]*(C-2)%P;
for (i=4;i<=N;i++)
f[i] = f[i-1]*(C-2)+f[i-2]*(C-1),f[i]%=P;
init(N);
tot = 0;
for (i=1;i<N;i++)
{
scanf("%d%d",&a,&b);
a--,b--;
insert(a,b);
insert(b,a);
}
for (i=0;i<M;i++){
scanf("%d%d",&a,&b);
a--,b--;
Q[a].push_back(make_pair(b,i));
Q[b].push_back(make_pair(a,i));
}
dfs(0,-1);
LCA(0);
long long oldans = C*mul(C-1,N-1,P)%P;
for (i=0;i<M;i++){
ans[i]++;
//printf("%d-------%d %d\n",ans[i],int(f[ans[i]]),int(mul(C-1,N-ans[i],P)));
long long nowans = f[ans[i]]*mul(C-1,N-ans[i],P)%P;
printf("%d\n",int((oldans+P-nowans)%P));
}
}
}
}}}题意：一棵树，C种颜色给出若干询问，每次询问是若在树上加一条边，对树上的点进行染色，有边相邻的两点不能同色，问染色方案比原来少了多少。
首先知道一棵点数为N的树染色方案数是C*(C-1)(N-1)，如果连边的话，变成一个环作为root的树，这时总方案数就是环的染色方案*(C-1)^(left_nodes)
现在问题是快速求得连边后的环中顶点个数，用LCA可以离线求得。
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
int node[400000],next[400000],edge[100000],tot;
int father[100000],ans[100000];
bool lcavis[100000],visit[100000];
void insert(int a,int b){
node[tot] = b,next[tot]=edge[a],edge[a] = tot++;
}
int depth[50000];
#define PII pair<int,int>
vector<PII> Q[50000];
void init(int N){
for (int i=0;i<N;i++)
father[i] = i,Q[i].clear(),edge[i] = -1,lcavis[i] = visit[i] = false;
}
int findroot(int x){
if (father[x]==x) return x;
else return father[x] = findroot(father[x]);
}
void Unoin(int a,int b){
int fa = findroot(a);
int fb = findroot(b);
father[fa] = fb;
}
void calc(int v){
int t = Q[v].size();
for (int i=0;i<t;i++)
{
int u = Q[v][i].first;
if (!visit[u]) continue;
ans[Q[v][i].second] = depth[u]+depth[v]-2*depth[findroot(u)];
}
}
void LCA(int v){
lcavis[v] = true;
for (int i=edge[v];i!=-1;i=next[i]){
if (!lcavis[node[i]]){
LCA(node[i]);
Unoin(node[i],v);
}
}
visit[v] = true;
calc(v);
}
void dfs(int now,int fa){
if (fa==-1) depth[now] = 0;
else
depth[now] = depth[fa]+1;
for (int i=edge[now];i!=-1;i=next[i])
if (node[i]!=fa)
dfs(node[i],now);
}
long long mul(int n,int m,int P){
long long ans = 1,r = n;
while(m){
if (m&1) ans*=r,ans%=P;
r*=r;
r%=P;
m>>=1;
}
return ans;
}
int N,M,C,P;
long long f[60000];
int main(){
int i,a,b;
while(scanf("%d%d%d%d",&N,&M,&C,&P)!=EOF){
f[1] = 1LL*C%P,f[2] = 1LL*C*(C-1)%P,f[3] = f[2]*(C-2)%P;
for (i=4;i<=N;i++)
f[i] = f[i-1]*(C-2)+f[i-2]*(C-1),f[i]%=P;
init(N);
tot = 0;
for (i=1;i<N;i++)
{
scanf("%d%d",&a,&b);
a--,b--;
insert(a,b);
insert(b,a);
}
for (i=0;i<M;i++){
scanf("%d%d",&a,&b);
a--,b--;
Q[a].push_back(make_pair(b,i));
Q[b].push_back(make_pair(a,i));
}
dfs(0,-1);
LCA(0);
long long oldans = C*mul(C-1,N-1,P)%P;
for (i=0;i<M;i++){
ans[i]++;
//printf("%d-------%d %d\n",ans[i],int(f[ans[i]]),int(mul(C-1,N-ans[i],P)));
long long nowans = f[ans[i]]*mul(C-1,N-ans[i],P)%P;
printf("%d\n",int((oldans+P-nowans)%P));
}
}
}