F. Wildflower - 题解
比赛与标签
比赛: Codeforces Round 1029 (Div. 3) 标签: combinatorics, dfs and similar, trees 难度: *1800
题目大意喵~
有一棵有 n 个节点的树，根节点是 1。我们需要给每个节点 i 赋一个值 a_i，这个值可以是 1 或者 2。
对于树上的任意一个节点 u，我们定义它的“子树和” s_u 为它子树中所有节点（包括 u 自己）的 a_v 值的总和。
我们的任务是，找出有多少种不同的数组 a（也就是给每个节点赋值的方案），可以使得所有节点的子树和 s_u 都是独一无二的（即两两不相等）。
因为答案可能很大，所以要对 10^9 + 7 取模哦。
简单来说，就是给树上每个点染上颜色 1 或 2，要求所有子树的“颜色值之和”互不相同，问有多少种染色方案，喵~
解题思路大揭秘！
这道题看起来像个复杂的组合计数问题，直接去计算所有情况然后检查是否满足条件，肯定会超时的说。所以，我们得找到问题的突破口！
关键的第一步：什么情况下子树和会冲突？
一个非常重要的性质是：如果节点 u 是节点 v 的祖先，那么 v 的子树完全包含在 u 的子树里。这意味着 s_u 一定会比 s_v 大（因为 s_u 至少比 s_v 多了一个 a_u 的值，而 a_u 最小也是1）。所以，祖先和后代的子树和永远不会相等！
这样一来，我们只需要担心那些互相没有祖先-后代关系的节点对了，比如兄弟节点，或者堂兄弟节点等等。
第二步：从树的结构入手！
既然问题和树的结构息息相关，那我们就来分析一下树的“形状”吧！
为了方便处理，代码用了一个很可爱的小技巧：创建一个虚拟节点 0，并把它和根节点 1 连接起来。这样，整棵树就变成了一个无根树，根节点 1 也不再特殊，方便我们统一处理所有节点的度。
最简单的情况：一条链（竹子树） 如果这棵树（在加入虚拟节点
0后）所有节点的度数都小于等于2，那它就是一条长长的链。在原来的有根树里，这就意味着它是一条从根节点出发的“竹子”。在这种结构下，任意两个节点都存在祖先-后代关系。根据我们刚才的发现，它们的子树和不可能相等！所以，任何一种赋值方案都是合法的。每个节点有2种选择（1或2），总共有n个节点，所以答案就是2^n种啦！太复杂的情况：直接说“不” 如果树的结构太复杂，比如说某个节点的度数大于
3，或者有两个或以上度数为3的节点，会发生什么呢？ 想象一个节点u，它有4个邻居。在有根树的视角下，这可能意味着它有4个孩子，或者3个孩子和1个父亲。如果它有4个孩子都是叶子节点，那这4个叶子节点的子树大小都是1，它们的子树和s只能是1或2。根据鸽巢原理，要把4个s值放进{1, 2}这两个篮子里，必然会有重复的！所以，这种情况直接就是0种方案。可以证明，只要度数大于3或者度为3的节点多于一个，就总能找到无法避免的冲突。所以，答案是0！唯一有趣的情况：一个“三岔路口” 现在只剩下一种可能了：整棵树只有一个节点的度数是
3（我们叫它triNode），其他所有节点的度数都小于等于3。这棵树就像一条主路，在triNode这个地方分出了三个岔路。这三个岔路（或者说分支）是冲突的主要来源。解题的关键，就在于分析这三个分支的“大小”。代码里通过一次
BFS（或queue模拟）和一次后序遍历，巧妙地计算出了以1为根时所有节点的子树大小。然后，对于我们的三岔路口节点
triNode，它的三个邻居v1, v2, v3分别通向三个分支。一个神奇的发现是，决定最终答案的，似乎是这三个邻居各自的子树大小！我们把这三个子树大小记为a, b, c。- 注意：这里的子树大小
size(v)是在原树（根为1）的定义下计算的。如果v是triNode的父节点，size(v)会包含triNode的子树。代码里直接取size(v)(sub_arr[v]+1) 作为分支的特征值，虽然看起来有点怪，但它确实是解题的关键！
我们把这三个大小值
a, b, c从小到大排序，得到mn, mid, mx。- 如果
mn == mid：这说明最小的两个分支“大小”相等，冲突的风险更高！经过一番复杂的推导（小猫娘的脑袋要炸了喵>_<），可以得出方案数是2 * 2^(n - 2*mn)。 - 如果
mn != mid：两个最小分支“大小”不同，情况稍微好一些。方案数是2^(n - 2*mn - 1) + 2^(n - 2*mn)。
这个公式的直观理解是，
2*mn大概代表了两个最小分支中被约束的节点范围，剩下的n - 2*mn个节点相对自由。而前面的系数2或者1+2（通过pow2提取公因式）则代表了解决这两个小分支间冲突的有效“元配置”数量。- 注意：这里的子树大小
总结一下我们的策略：
- 计算每个节点的度数（在加了虚拟节点
0的图上）。 - 如果最大度数
>3或 度为3的节点>1，答案是0。 - 如果没有度为
3的节点，答案是2^n。 - 如果只有一个度为
3的节点triNode，计算它三个邻居的子树大小a,b,c，排序得到mn, mid, mx，然后套用公式！
是不是感觉清晰多啦？喵~
代码实现喵！
// 完整的AC代码，添加详细注释解释关键逻辑
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
// 模数
const int MOD = 1000000007;
// n的最大值
const int MAX_N = 200000;
// 预处理2的幂，方便后面计算，避免重复计算和取模的麻烦
vector<long long> pow2(MAX_N + 1);
int main() {
// 加速输入输出，对付大数据量的法宝喵~
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 预计算2的幂
pow2[0] = 1;
for (int i = 1; i <= MAX_N; i++) {
pow2[i] = (pow2[i - 1] * 2) % MOD;
}
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<vector<int>> g(n + 1);
vector<int> deg(n + 1, 0);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
deg[u]++;
deg[v]++;
}
// 引入一个虚拟节点0，连接到根节点1。
// 这样可以把树当作无根树来处理度数，避免对根节点1的特殊判断。
g[0].push_back(1);
g[1].push_back(0);
deg[0]++;
deg[1]++;
int mxDeg = 0; // 记录最大度数
int triCnt = 0; // 记录度数为3的节点数量
int triNode = -1; // 记录那个唯一的度为3的节点
for (int i = 1; i <= n; i++) {
if (deg[i] > mxDeg) mxDeg = deg[i];
if (deg[i] == 3) {
triCnt++;
triNode = i;
}
}
// 如果最大度数>3，或者度为3的节点超过1个，必然有冲突，方案数为0
if (mxDeg > 3 || triCnt > 1) {
cout << 0 << '\n';
continue;
}
// 如果没有度为3的节点，说明树是条链，任何方案都合法
if (triCnt == 0) {
cout << pow2[n] << '\n';
continue;
}
// --- 处理只有一个度为3节点的情况 ---
// parent_arr[i] 记录在以1为根的树中，i的父节点是谁
vector<int> parent_arr(n + 1, -1);
// sub_arr[i] 记录以i为根的子树的大小减1
vector<long long> sub_arr(n + 1, 0);
vector<int> order; // 存储遍历顺序
queue<int> q;
// 1. BFS确定父子关系和遍历顺序
q.push(1);
parent_arr[1] = 0; // 1的父亲是虚拟节点0
while (!q.empty()) {
int u = q.front(); q.pop();
order.push_back(u);
for (int v : g[u]) {
if (v == parent_arr[u]) continue;
parent_arr[v] = u;
q.push(v);
}
}
// 2. 反转遍历顺序，得到后序遍历，从叶子节点开始计算子树大小
reverse(order.begin(), order.end());
for (int u : order) {
for (int v : g[u]) {
if (v == parent_arr[u]) continue;
// 子树大小 = 所有子节点的子树大小之和 + 1
// 这里 sub_arr[u] = size(u)-1
sub_arr[u] += 1 + sub_arr[v];
}
}
sub_arr[0] = n; // 虚拟节点的子树是整棵树
// 3. 找到triNode的三个分支的特征值（即其邻居的子树大小）
vector<long long> branch;
for (int v : g[triNode]) {
branch.push_back(sub_arr[v] + 1);
}
// 4. 排序这三个值
long long a = branch[0], b = branch[1], c = branch[2];
long long mn = min({a, b, c});
long long mx = max({a, b, c});
long long mid = a + b + c - mn - mx;
// 5. 根据公式计算答案
long long ans;
if (mn == mid) { // 最小的两个分支大小相等
ans = (2 * pow2[n - 2 * mn]) % MOD;
} else { // 最小的两个分支大小不等
ans = (pow2[n - 2 * mn - 1] + pow2[n - 2 * mn]) % MOD;
}
cout << ans << '\n';
}
return 0;
}复杂度分析的说
- 时间复杂度: O(N) 的说。其中
N是所有测试用例的n的总和。对于每个测试用例，我们需要建图、计算度数、BFS、后序遍历，这些操作都是线性的，即 O(n)。因为所有n的总和有上限，所以总时间复杂度是线性的。 - 空间复杂度: O(N) 的说。我们需要存储图的邻接表、度数数组、父节点数组、子树大小数组等，这些都需要 O(n) 的空间。
知识点与总结
这道题真是一次愉快的狩猎之旅呢！我们捕获了这些知识点：
- 树形问题的结构分析: 解决很多树上问题的关键是先分析树的结构特性。通过度数分析，我们把一个复杂问题划分成了几种简单的情况，这是非常高效的解题思路。
- 虚拟节点技巧: 在处理有根树问题时，引入一个虚拟节点连接到根，有时能将根的特殊情况一般化，让代码更简洁优美。
- 组合思想与鸽巢原理: “最大度数>3则无解”的判断，背后是朴素但强大的鸽巢原理。
- DFS/BFS应用: 使用 BFS (或类似方法) 建立父子关系，再用后序遍历（通过反转BFS序得到）自底向上地进行DP或计算（如此题中的子树大小），是树形问题的经典操作。
- 观察与归纳: 最终的计算公式可能难以严格证明，但在比赛中，通过分析特殊情况、寻找规律并大胆猜测，也是一种重要的能力哦！
希望这篇题解能帮到大家！解题就像寻宝，每一步的发现都让人心动不已。大家要继续加油，享受算法的乐趣哦！喵~