team2012-D1-sol-0015

从 Trac 迁移的文章

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

原文章内容如下：

=== 题目大意 ===
给出 n 个结点的一棵树. 每个结点可以用 C 种颜色中的一种去染色. 要求有边直接相连的两个结点不能染成同一种颜色. 这棵树有一个染色方案数 sum. 然后给出 M 个询问, 每个询问会在树上加一条边, 问加上这条边之后染色方案数会减少多少种.

=== 数据范围 ===
 * 1 <= N <= 50000
 * 1 <= M <= 100000
 * 1 <= C <= 100000

=== 解题思路 ===
又是搞学长出的"树上加一条边"系列题目 (吐槽: 搞学长你就这么喜欢章鱼图么? 就这么喜欢么? 嗯? = =b). 首先考虑怎么算一棵树上的方案数. 由于每次加入一个新的结点, 肯定和且仅和一个结点有边直接相连, 所以只要和那个结点的颜色不一样就可以了, 于是第一个结点有 C 种染色方法, 而后来加入的每个结点都有 C-1 种染色方法. 于是一棵 n 个结点的树的染色方法数 sum = C * (C-1)^n-1^. 然后在一棵树上加一条边会形成一个圈, 然后以圈上的每个结点为根, 各自延伸出一棵子树. 所以只要先求出加边后圈上的结点数 K, 再求出 K 个结点的圈的方案数 cnt, 那么加边后的方案数就是 cnt * (C-1)^n-k^.

求 K 个结点的圈的方案数 cnt[K] 是用递推的方法: cnt[K] = cnt[K-2] * (C-1) + cnt[K-1] * (C-2), (K >= 4). 初始化: cnt[2] = C * (C-1), cnt[3] = cnt[2] * (C-2). 当然了如果加边后圈的大小只有 2, 那么减少就是 0, 因为没有加了跟没加一样, 这里要特判一下. 

题目大意

给出 n 个结点的一棵树. 每个结点可以用 C 种颜色中的一种去染色. 要求有边直接相连的两个结点不能染成同一种颜色. 这棵树有一个染色方案数 sum. 然后给出 M 个询问, 每个询问会在树上加一条边, 问加上这条边之后染色方案数会减少多少种.

数据范围

• 1 <= N <= 50000
• 1 <= M <= 100000
• 1 <= C <= 100000

解题思路

又是搞学长出的"树上加一条边"系列题目 (吐槽: 搞学长你就这么喜欢章鱼图么? 就这么喜欢么? 嗯? = =b). 首先考虑怎么算一棵树上的方案数. 由于每次加入一个新的结点, 肯定和且仅和一个结点有边直接相连, 所以只要和那个结点的颜色不一样就可以了, 于是第一个结点有 C 种染色方法, 而后来加入的每个结点都有 C-1 种染色方法. 于是一棵 n 个结点的树的染色方法数 sum = C * (C-1)^n-1. 然后在一棵树上加一条边会形成一个圈, 然后以圈上的每个结点为根, 各自延伸出一棵子树. 所以只要先求出加边后圈上的结点数 K, 再求出 K 个结点的圈的方案数 cnt, 那么加边后的方案数就是 cnt * (C-1)^n-k.

求 K 个结点的圈的方案数 cnt[K] 是用递推的方法: cnt[K] = cnt[K-2] * (C-1) + cnt[K-1] * (C-2), (K >= 4). 初始化: cnt[2] = C * (C-1), cnt[3] = cnt[2] * (C-2). 当然了如果加边后圈的大小只有 2, 那么减少就是 0, 因为没有加了跟没加一样, 这里要特判一下.