树上赋权 - 题解

标签与难度

标签: 树形结构, 深度优先搜索 (DFS), 构造, 贪心, 图论, 思维题难度: 1700

题目大意喵~

主人你好呀~！这道题是这样的呐：

我们有一棵 $N$ 个点的树，根节点是 $1$ 号点。我们的任务是给树上的每一个点都赋上一个权值，可以是 $0$ 或者 $1$ 。

赋完权值之后，我们要计算两种特殊的子树数量：

全0子树：子树里所有点的权值都是 $0$ 。
全1子树：子树里所有点的权值都是 $1$ 。

我们的目标是，找到一种赋权方案，使得这两种子树的数量完全相等！

如果能找到这样的方案，就输出 "YES"，然后给出任意一种合法的方案（也就是每个点的权值）。如果找不到，就伤心地输出 "NO"，喵~

解题思路分析

这道题看起来是要我们去构造一种满足条件的方案，而不是去计算所有方案数，这通常意味着存在一些巧妙的性质或者贪心策略，喵~ 让我们一起动动小脑筋，把问题抽丝剥茧吧！

关键突破口：谁对计数有贡献？

一个以节点 $u$ 为根的子树，要成为“全0子树”或“全1子树”（我们叫它“单色子树”好了），需要 $u$ 和它所有的后代节点都拥有相同的颜色（权值）。这是一个非常强的约束条件呢！

那么，什么样的节点最容易形成单色子tree呢？当然是叶子节点啦！

一个叶子节点，它没有孩子，它的子树就只包含它自己。所以，只要给一个叶子节点赋权为 $0$ ，它就立刻贡献了一个“全0子树”；赋权为 $1$ ，就贡献了一个“全1子树”。这是板上钉钉的事情，喵~

核心洞察：每个叶子节点都必然会贡献一个单色子树。

简化问题：只让叶子节点贡献

既然非叶子节点形成单色子树的条件那么苛刻，我们能不能构造一种方案，使得所有非叶子节点的子树都不是单色的？这样一来，我们只需要关心叶子节点的贡献就行啦！

如何让一个非叶子节点 $u$ 的子树不是单色的呢？很简单，只要让 $u$ 和它的某一个孩子 $v$ 的权值不同（即 val[u] != val[v]），那么以 $u$ 为根的子树就不可能是单色的了。

基于这个思路，我们的策略就清晰了：

我们只通过给叶子节点赋权来产生单色子树。
对于所有非叶子节点，我们通过巧妙的赋值来破坏它们的单色性。

设这棵树一共有 $L$ 个叶子节点。根据我们的策略，总共就会产生 $L$ 个单色子树。为了让全0和全1的子树数量相等，我们必须给 $L/2$ 个叶子赋权 $0$ ，给另外 $L/2$ 个叶子赋权 $1$ 。

这就引出了一个非常重要的分类讨论，是根据叶子节点数量 $L$ 的奇偶性来的！

情况一：叶子数量 $L$ 是偶数 (Happy Case ฅ'ω'ฅ)

如果叶子节点的数量 $L$ 是偶数，那真是太棒了！我们可以：

选出 $L/2$ 个叶子，把它们的权值设为 $0$ 。
把剩下 $L/2$ 个叶子，权值设为 $1$ 。这样，来自叶子节点的贡献就完美平衡了。

接下来，我们处理非叶子节点。我们可以从叶子开始，一层层往上确定父节点的权值。对于一个已经确定权值的节点 $v$ ，我们可以把它父节点 $u$ 的权值设为 $1 - val[v]$ 。这样就保证了 $u$ 和 $v$ 的权值不同，成功破坏了 $u$ 子树的单色性。这个过程可以通过一次从下到上的 DFS（后序遍历）轻松实现。

所以，当叶子数量为偶数时，总是有解的！

情况二：叶子数量 $L$ 是奇数 (Tricky Case >_<)

当 $L$ 是奇数时，我们就不能简单地平分了。比如，我们会有 $(L+1)/2$ 个 $0$ 和 $(L-1)/2$ 个 $1$ ，或者反过来。总之会差一个。

怎么办呢？只靠叶子节点已经无法平衡了。我们必须引入一个非叶子节点来贡献一个单色子树，从而让总的单色子树数量变成 $L+1$ （这是一个偶数！），这样就有机会平分了！

假设我们决定额外创造一个“全0子树”。我们需要选择一个非叶子节点 $u$ ，把它和它子树里的所有节点都染成 $0$ 。

这会为我们增加 $1$ 个全0子树（由 $u$ 贡献）。
假设 $u$ 的子树里有 $k$ 个叶子节点。这些叶子节点现在都被强制染成了 $0$ ，它们会贡献 $k$ 个全0子树。
于是，通过“占领” $u$ 的子树，我们获得了 $1+k$ 个全0子树。

现在，我们的目标是让全0子树和全1子树的数量都达到 $(L+1)/2$ 。

我们已经有了 $1+k$ 个全0子树。还需要 (L+1)/2 - (1+k) 个全0子树。
我们目前有 $0$ 个全1子树。还需要 (L+1)/2 个全1子树。

这些额外的需求，都需要由剩下那 $L-k$ 个不在 $u$ 子树里的“自由”叶子来满足。

我们需要把 (L+1)/2 - (1+k) 个自由叶子染成 $0$ 。
我们需要把 (L+1)/2 个自由叶子染成 $1$ 。

这两个数量加起来必须等于自由叶子的总数 $L-k$ ：

\left(\frac{L+1}{2} - (1+k)\right) + \left(\frac{L+1}{2}\right) = \frac{2(L+1)}{2} - 1 - k = L+1-1-k = L-k

等式成立！这说明只要数量非负，这个分配就是可行的。

所以，唯一的限制是，我们需要分配的染成 $0$ 的自由叶子数量不能是负数：

\frac{L+1}{2} - (1+k) \ge 0 \\ \frac{L-1}{2} - k \ge 0 \\ k \le \frac{L-1}{2}

这就是我们的魔法咒语！当 $L$ 为奇数时，我们需要找到一个非叶子节点 $u$ ，它子树中的叶子数量 $k$ 满足 $k \le (L-1)/2$ 。

为了让这个条件更容易满足，我们应该贪心地选择一个 $k$ 最小的候选节点 $u$ 。什么样的节点 $u$ 的子树包含的叶子最少呢？直觉上，是那些“离叶子最近”的节点，也就是所有孩子都是叶子节点的那些节点。

所以，奇数情况下的策略是：

找到所有“孩子全是叶子”的非叶子节点。
在它们当中，找到一个子树叶子数 $k$ 最小的节点，记为 $u_{best}$ ，其叶子数为 $k_{min}$ 。
如果 $k_{min} \le (L-1)/2$ $k_{min} \leq (L - 1) /2$ ，太棒了！我们有解！
- 将 $u_{best}$ 和它子树里的所有节点染成 $0$ 。
- 在剩下的自由叶子中，将 $(L-1)/2 - k_{min}$ 个染成 $0$ ，将 $(L+1)/2$ 个染成 $1$ 。
- 像偶数情况一样，向上填充其他所有节点的权值。
如果连最小的 $k_{min}$ 都大于 $(L-1)/2$ ，那就说明谁也满足不了条件，我们只能遗憾地宣布 "NO" 了，喵呜~

好啦，思路整理完毕，我们可以开始写代码了！

代码实现

这是我根据上面的思路，精心重构的一份代码，注释超详细的哦！希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

// 使用邻接表来存储树的结构，喵~
std::vector<int> adj[100005];
// parent[i] 存节点i的父节点
int parent[100005];
// leaves_in_subtree[i] 存以i为根的子树中叶子的数量
int leaves_in_subtree[100005];
// is_leaf[i] 判断节点i是不是叶子
bool is_leaf[100005];
// val[i] 是我们最终要赋的权值 (0 或 1)
// 初始化为-1表示还没赋值
int val[100005];
int n;

// 第一次DFS：预处理信息
// 计算每个节点的父节点、是否是叶子、以及子树中的叶子数量
void dfs_precompute(int u, int p) {
    parent[u] = p;
    is_leaf[u] = true; // 先假设是叶子
    leaves_in_subtree[u] = 0;

    for (int v : adj[u]) {
        if (v == p) continue;
        is_leaf[u] = false; // 有孩子，就不是叶子了
        dfs_precompute(v, u);
        leaves_in_subtree[u] += leaves_in_subtree[v];
    }

    if (is_leaf[u]) {
        leaves_in_subtree[u] = 1;
    }
}

// 第二次DFS：从下往上填充权值
// 确保非叶子节点的子树不都是单色的
void dfs_propagate_val(int u, int p) {
    // 先递归处理所有孩子
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs_propagate_val(v, u);
    }

    // 如果当前节点是根节点，或者它的权值已经被确定了，就不用管啦
    if (u == 1 || val[u] != -1) return;

    // 找到一个孩子v，根据v的权值来确定u的权值
    // 这样可以保证 val[u] != val[v]，打破单色性
    int child_to_use = -1;
    for (int v : adj[u]) {
        if (v == p) continue;
        child_to_use = v;
        break;
    }
    
    // 如果它有孩子（即非叶子），就用孩子的权值来反向赋值
    if (child_to_use != -1) {
        val[u] = 1 - val[child_to_use];
    }
}

// 这是一个辅助函数，用来把一个节点和它的所有孩子都染成一个颜色
// 用在奇数情况下的特殊处理
void color_subtree_of_leaf_parent(int u, int color) {
    val[u] = color;
    for (int v : adj[u]) {
        if (v != parent[u]) {
            val[v] = color;
        }
    }
}

void solve() {
    std::cin >> n;
    if (n == 1) { // 只有一个点，无所谓0和1，但题目要求相等，0个=0个，所以YES
        std::cout << "YES\n0\n";
        return;
    }
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 初始化所有节点的权值为-1
    std::fill(val + 1, val + n + 1, -1);

    // 预处理
    dfs_precompute(1, 0);

    // 收集所有叶子节点
    std::vector<int> leaves;
    for (int i = 1; i <= n; ++i) {
        if (is_leaf[i]) {
            leaves.push_back(i);
        }
    }

    int num_leaves = leaves.size();

    if (num_leaves % 2 == 0) { // 叶子数量是偶数，好办！
        std::cout << "YES\n";
        int half = num_leaves / 2;
        for (int i = 0; i < half; ++i) val[leaves[i]] = 0;
        for (int i = half; i < num_leaves; ++i) val[leaves[i]] = 1;
    } else { // 叶子数量是奇数，有点麻烦
        int best_node = -1;
        int min_leaves = n + 1;

        // 寻找最优的非叶子节点u (它的孩子都是叶子)
        for (int i = 1; i <= n; ++i) {
            if (is_leaf[i]) continue;
            
            bool all_children_are_leaves = true;
            for (int v : adj[i]) {
                if (v == parent[i]) continue;
                if (!is_leaf[v]) {
                    all_children_are_leaves = false;
                    break;
                }
            }

            if (all_children_are_leaves) {
                if (leaves_in_subtree[i] < min_leaves) {
                    min_leaves = leaves_in_subtree[i];
                    best_node = i;
                }
            }
        }
        
        // 检查是否满足条件 k <= (L-1)/2
        if (best_node == -1 || min_leaves > (num_leaves - 1) / 2) {
            std::cout << "NO\n";
            return;
        }

        std::cout << "YES\n";
        // 把找到的最优节点u和它的孩子们染成0
        color_subtree_of_leaf_parent(best_node, 0);

        // 确定需要多少个0和1
        int needed_zeros = (num_leaves - 1) / 2 - min_leaves;
        int needed_ones = (num_leaves + 1) / 2;

        // 给剩下的自由叶子染色
        for (int leaf_node : leaves) {
            if (val[leaf_node] == -1) { // 如果这个叶子还没被染色
                if (needed_zeros > 0) {
                    val[leaf_node] = 0;
                    needed_zeros--;
                } else {
                    val[leaf_node] = 1;
                    needed_ones--;
                }
            }
        }
    }

    // 填充剩余所有节点的权值
    dfs_propagate_val(1, 0);
    
    // 根节点可能还没赋值，随便给一个和它孩子不同的值
    if (val[1] == -1) {
        val[1] = 1 - val[adj[1][0]];
    }

    // 输出最终答案
    for (int i = 1; i <= n; ++i) {
        std::cout << val[i] << (i == n ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    solve();
    return 0;
}

复杂度分析

时间复杂度: $O(N)$ 整个算法的核心是两次DFS遍历。第一次 dfs_precompute 访问每个节点和每条边一次，复杂度是 $O(N)$ 。之后收集叶子、寻找最佳节点等操作都可以在 $O(N)$ 内完成。第二次 dfs_propagate_val 同样是 $O(N)$ 。所以总的时间复杂度是线性的，非常高效哦，喵~
空间复杂度: $O(N)$ 我们使用了邻接表来存图，占用了 $O(N)$ 的空间。parent, leaves_in_subtree, is_leaf, val 这些辅助数组也都是 $O(N)$ 的大小。DFS的递归栈深度在最坏情况下（一条链）也是 $O(N)$ 。所以总的空间复杂度是 $O(N)$ 。

知识点总结

这道题真是一次有趣的思维探险呢！我们来总结一下收获吧：

抓住问题核心: 解决构造题的关键往往是找到最简单、最核心的贡献者。在这里，就是叶子节点。它们的贡献是确定且直接的。
分类讨论思想: 根据核心要素（叶子数量的奇偶性）将问题分解成更简单、清晰的子问题，是解决复杂问题的常用技巧。
构造性思维: 与其去验证一个给定的方案，不如主动去构建一个满足条件的方案。我们的策略“只让叶子贡献”和“破坏非叶子节点的单色性”就是典型的构造思想。
贪心选择: 在奇数情况下，为了让 k <= (L-1)/2 这个条件尽可能成立，我们贪心地选择了拥有最少叶子节点的子树，这体现了贪心算法的思想。
DFS的灵活运用: 我们用了两次DFS，一次是自顶向下传递信息并自底向上汇总（dfs_precompute），一次是纯粹的自底向上进行赋值（dfs_propagate_val），展示了DFS在树形问题中的强大能力。

希望这篇题解能对主人有所帮助！解题就像寻宝，只要找到正确的线索，就一定能找到答案的，加油喵~！

树上赋权 - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

关键突破口：谁对计数有贡献？ ​

简化问题：只让叶子节点贡献 ​

情况一：叶子数量 LLL 是偶数 (Happy Case ฅ'ω'ฅ) ​

情况二：叶子数量 LLL 是奇数 (Tricky Case >_<) ​

代码实现 ​

复杂度分析 ​

知识点总结 ​