tkdsheep-solution-0015

从 Trac 迁移的文章

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

原文章内容如下：

{{{
给一棵n个点的树，以及C种颜色，要在树上给每个点染色，并且直接相连的两个点不能有相同颜色
然后现在有很多次查询，每次查询问的是如果在树上再加一条边，染色方案数会减少多少

一步一步分析这个问题，首先如果只是一条链上的n个点，首先随便选一个初始点，它有C种颜色可以染
然后其他点就只有C-1种颜色可用了，所以答案是C*（C-1）^n-1

树上的情况其实和链是一样的，自己想一下就明白了，因为一个点最多之和两个点相连

现在在树上加一条边，实际就变成来一个“章鱼树”，即中间一个环，环上的某些点延伸出很多棵子树
设总共有n个点，环上的点有m个，f[m]表示m个点构成的环有多少种染色方案
则剩下的n-m个点（章鱼腿上的点）每个点都有C-1种颜色可选，所以答案就是f[m]*（C-1）^n-m

那么如何快速求出加边之后，得到的环有多少个点？设加进去的边的两个端点是u和v
则环上点的个数为 d[u]+d[v]-2*d[lca(u,v)]+1
数组d表示节点的深度（到根节点的距离），其中d[root]=1，lca则为u和v的最近公共祖先

所以可以在logn的时间求出环上点的个数

那么f[i]怎么计算呢？

f[i] = f[i-1]*(C-2)+f[i-2]*(C-1) （i>=4)

为什么是这样推的？自己画一下就知道了。。。跟错排公式的推法有点类似吧

}}}



{{{
附：

LCA离线tarjan伪代码

//parent为并查集，FIND为并查集的查找操作

//QUERY为询问结点对集合

//TREE为基图有根树 

Tarjan(u)      

    visit[u] = true   

    for each (u, v) in QUERY     

        if visit[v]    

        ans(u, v) = FIND(v)   

    for each (u, v) in TREE    

        if !visit[v]        

            Tarjan(v)   

            parent[v] = u

}}}

给一棵n个点的树，以及C种颜色，要在树上给每个点染色，并且直接相连的两个点不能有相同颜色
然后现在有很多次查询，每次查询问的是如果在树上再加一条边，染色方案数会减少多少
一步一步分析这个问题，首先如果只是一条链上的n个点，首先随便选一个初始点，它有C种颜色可以染
然后其他点就只有C-1种颜色可用了，所以答案是C*（C-1）^n-1
树上的情况其实和链是一样的，自己想一下就明白了，因为一个点最多之和两个点相连
现在在树上加一条边，实际就变成来一个“章鱼树”，即中间一个环，环上的某些点延伸出很多棵子树
设总共有n个点，环上的点有m个，f[m]表示m个点构成的环有多少种染色方案
则剩下的n-m个点（章鱼腿上的点）每个点都有C-1种颜色可选，所以答案就是f[m]*（C-1）^n-m
那么如何快速求出加边之后，得到的环有多少个点？设加进去的边的两个端点是u和v
则环上点的个数为 d[u]+d[v]-2*d[lca(u,v)]+1
数组d表示节点的深度（到根节点的距离），其中d[root]=1，lca则为u和v的最近公共祖先
所以可以在logn的时间求出环上点的个数
那么f[i]怎么计算呢？
f[i] = f[i-1]*(C-2)+f[i-2]*(C-1) （i>=4)
为什么是这样推的？自己画一下就知道了。。。跟错排公式的推法有点类似吧

附：
LCA离线tarjan伪代码
//parent为并查集，FIND为并查集的查找操作
//QUERY为询问结点对集合
//TREE为基图有根树 
Tarjan(u)      
    visit[u] = true   
    for each (u, v) in QUERY     
        if visit[v]    
        ans(u, v) = FIND(v)   
    for each (u, v) in TREE    
        if !visit[v]        
            Tarjan(v)   
            parent[v] = u