team2012-F3-sol-0015

从 Trac 迁移的文章

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

原文章内容如下：

{{{
题意：给定一个树，每个节点可以染成c种颜色，但是相邻颜色不能相同，若从这树上添加一条边，染色方案减少多少？
解法：在添加边之前，根可以染c种颜色，其余每个节点保证与父亲不同，染色方案总数为c*[(c-1)^(n-1)]
若添加一条边(a,b)，形成一个环a->b->lca(a,b)->a，在这个环上染色使得相邻不相同的方案数设为Fi，其中i是环上的节点数
则从环上第一个节点开始染色，染到第i-1个节点时，若i-1的颜色与1相同，则第i个有c-1种染法
此时将1和i-1连接起来作为一个点，形成一个长为i-2的环，在这环上要保证相邻异色，有F(i-2)种方案
所以若i-1的颜色与1相同，有F(i-2)*(c-1)种
同理，若i-1的颜色与1不相同，则第i个有c-2种染法，将1和i-1连接起来形成一个长为i-1的环，有F(i-1)种方案
所以若i-1的颜色与1不相同，有F(i-1)*(c-2)种
所以Fi = F(i-2)*(c-1) + F(i-1)*(c-2)
环的长度为 depth[a] + depth[b] - 2*depth[lca(a,b)] + 1
在环外的“枝”上逐步染色，其余的点均要保证不与前一个同色，还要乘上(c-1)^(n-circle_length)种
将总数减去如上求得的方案数即为答案
}}}
{{{
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <cstring>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;

const int MAXN = 50005;
bool vis[MAXN];
vector<PII> query[MAXN];
vector<int> conn[MAXN];
int fa[MAXN], depth[MAXN];
LL f[MAXN], g[MAXN], tot;
LL ans[2*MAXN], MOD;
int n, m, c;

LL cal(int cir)
{
    LL ret = f[cir] * g[n-cir];
    ret %= MOD;
    ret = tot-ret;
    if(ret < 0)
        ret += MOD;
    return ret;
}

int find(int x)
{
    if(fa[x] == x)  return x;
    return fa[x] = find(fa[x]);
}

void dfs(int x)
{
    vis[x] = 1;
    for(int i=0;i<query[x].size();i++)
    {
        int v = query[x][i].first;
        if(vis[v])
        {
            int lca = find(v),
                cir = depth[x] + depth[v] - 2*depth[lca] + 1;
            ans[query[x][i].second] = cal(cir);
        }
    }
    for(int i=0;i<conn[x].size();i++)
    {
        int v = conn[x][i];
        if(!vis[v])
        {
            depth[v] = depth[x] + 1;
            dfs(v);
            fa[v] = x;
        }
    }
}

void gao()
{
    f[1] = 0;
    f[2] = 1LL*c*(c-1) % MOD;
    for(int i=3;i<=n;i++)
    {
        f[i] = f[i-1]*(c-2) + f[i-2]*(c-1);
        f[i] %= MOD;
    }
    g[0] = 1;
    for(int i=1;i<=n;i++)
    {
        g[i] = g[i-1]*(c-1);
        g[i] %= MOD;
    }
    tot = (c*g[n-1]) % MOD;

    for(int i=1;i<=n;i++)
        fa[i] = i;
    memset(vis, 0, sizeof(vis));
    depth[1] = 0;
    dfs(1);
    for(int i=1;i<=m;i++)
        printf("%lld\n", ans[i]);
}

int main()
{
    while(~scanf("%d %d %d %lld", &n, &m, &c, &MOD))
    {
        for(int i=1;i<=n;i++)
        {
            conn[i].clear();
            query[i].clear();
        }
        for(int i=1;i<n;i++)
        {
            int a, b;
            scanf("%d %d", &a, &b);
            conn[a].push_back(b);
            conn[b].push_back(a);
        }
        for(int i=1;i<=m;i++)
        {
            int a, b;
            scanf("%d %d", &a, &b);
            query[a].push_back(make_pair(b, i));
            query[b].push_back(make_pair(a, i));
        }
        gao();
    }
    return 0;
}
}}}

题意：给定一个树，每个节点可以染成c种颜色，但是相邻颜色不能相同，若从这树上添加一条边，染色方案减少多少？
解法：在添加边之前，根可以染c种颜色，其余每个节点保证与父亲不同，染色方案总数为c*[(c-1)^(n-1)]
若添加一条边(a,b)，形成一个环a->b->lca(a,b)->a，在这个环上染色使得相邻不相同的方案数设为Fi，其中i是环上的节点数
则从环上第一个节点开始染色，染到第i-1个节点时，若i-1的颜色与1相同，则第i个有c-1种染法
此时将1和i-1连接起来作为一个点，形成一个长为i-2的环，在这环上要保证相邻异色，有F(i-2)种方案
所以若i-1的颜色与1相同，有F(i-2)*(c-1)种
同理，若i-1的颜色与1不相同，则第i个有c-2种染法，将1和i-1连接起来形成一个长为i-1的环，有F(i-1)种方案
所以若i-1的颜色与1不相同，有F(i-1)*(c-2)种
所以Fi = F(i-2)*(c-1) + F(i-1)*(c-2)
环的长度为 depth[a] + depth[b] - 2*depth[lca(a,b)] + 1
在环外的“枝”上逐步染色，其余的点均要保证不与前一个同色，还要乘上(c-1)^(n-circle_length)种
将总数减去如上求得的方案数即为答案

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <cstring>
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int MAXN = 50005;
bool vis[MAXN];
vector<PII> query[MAXN];
vector<int> conn[MAXN];
int fa[MAXN], depth[MAXN];
LL f[MAXN], g[MAXN], tot;
LL ans[2*MAXN], MOD;
int n, m, c;
LL cal(int cir)
{
    LL ret = f[cir] * g[n-cir];
    ret %= MOD;
    ret = tot-ret;
    if(ret < 0)
        ret += MOD;
    return ret;
}
int find(int x)
{
    if(fa[x] == x)  return x;
    return fa[x] = find(fa[x]);
}
void dfs(int x)
{
    vis[x] = 1;
    for(int i=0;i<query[x].size();i++)
    {
        int v = query[x][i].first;
        if(vis[v])
        {
            int lca = find(v),
                cir = depth[x] + depth[v] - 2*depth[lca] + 1;
            ans[query[x][i].second] = cal(cir);
        }
    }
    for(int i=0;i<conn[x].size();i++)
    {
        int v = conn[x][i];
        if(!vis[v])
        {
            depth[v] = depth[x] + 1;
            dfs(v);
            fa[v] = x;
        }
    }
}
void gao()
{
    f[1] = 0;
    f[2] = 1LL*c*(c-1) % MOD;
    for(int i=3;i<=n;i++)
    {
        f[i] = f[i-1]*(c-2) + f[i-2]*(c-1);
        f[i] %= MOD;
    }
    g[0] = 1;
    for(int i=1;i<=n;i++)
    {
        g[i] = g[i-1]*(c-1);
        g[i] %= MOD;
    }
    tot = (c*g[n-1]) % MOD;
    for(int i=1;i<=n;i++)
        fa[i] = i;
    memset(vis, 0, sizeof(vis));
    depth[1] = 0;
    dfs(1);
    for(int i=1;i<=m;i++)
        printf("%lld\n", ans[i]);
}
int main()
{
    while(~scanf("%d %d %d %lld", &n, &m, &c, &MOD))
    {
        for(int i=1;i<=n;i++)
        {
            conn[i].clear();
            query[i].clear();
        }
        for(int i=1;i<n;i++)
        {
            int a, b;
            scanf("%d %d", &a, &b);
            conn[a].push_back(b);
            conn[b].push_back(a);
        }
        for(int i=1;i<=m;i++)
        {
            int a, b;
            scanf("%d %d", &a, &b);
            query[a].push_back(make_pair(b, i));
            query[b].push_back(make_pair(a, i));
        }
        gao();
    }
    return 0;
}