Moe's CF Life

Appearance

喵~ 主人，欢迎来到我的题解小屋！今天我们要解决的是一道关于树和异或的有趣问题，喵。别担心，我会一步一步引导你，让我们一起轻松地解决它吧！

题目大意 ​

我们有一棵有 n 个节点的树，每个节点 i 上都有一个整数 a_i。我们的目标是通过施展魔法，让所有节点上的数值都变得一样。

魔法是这样施展的：

  1. 首先，我们要选择一个节点 r 作为树的根。
  2. 然后，我们可以进行任意次数的操作。每次操作，我们可以选择任意一个节点 v 和一个非负整数 c。
  3. 施法后，对于节点 v 的子树（包括 v 自己）中的所有节点 i，它们上面的数值 a_i 都会变成 a_i ⊕ c。（这里的 ⊕ 是按位异或操作）。
  4. 每次操作的代价是 s * c，其中 s 是 v 子树的大小。

对于每一个可能的根节点 r (从 1 到 n)，我们都需要计算出让所有 a_i 相等的最小总代价，记为 m_r。最后，请输出 m_1, m_2, ..., m_n。

简单来说，就是对每个节点当一次根，算一下把整棵树的值都变成一样的最小花费是多少，喵~

解题思路 ​

这个问题看起来有点复杂，因为它涉及到选根、子树操作和最小化代价。但是别怕，我们可以把它拆解成几个小问题来思考，喵！

最终值该是多少？ ​

首先，我们要让所有节点的值都变成同一个数，我们叫它 X 吧。这个 X 到底应该是多少呢？

假设我们已经选定了根节点 r。对于任意一个非根节点 u 和它的父节点 p，我们想知道在 u 节点上应该施加什么魔法。 在 u 节点施加的魔法值为 c_u，在 p 节点施加的为 c_p，以此类推。 一个节点 u 的最终值，是它初始的 a_u 与它所有祖先（包括自己）施加的魔法值 c 的异或和。 也就是说，最终 a_u 会变成 a_u ⊕ c_u ⊕ c_{p} ⊕ c_{p的父} ⊕ ... ⊕ c_r。我们希望这个结果等于 X。

对于节点 u，我们有： a_u ⊕ c_u ⊕ c_{parent(u)} ⊕ ... ⊕ c_r = X

对于它的父节点 p，我们有： a_p ⊕ c_p ⊕ ... ⊕ c_r = X

把上面两个式子异或一下，好多项都消掉了，喵！ (a_u ⊕ c_u ⊕ c_p ⊕ ... ⊕ c_r) ⊕ (a_p ⊕ c_p ⊕ ... ⊕ c_r) = X ⊕ Xa_u ⊕ a_p ⊕ c_u = 0 所以，c_u = a_u ⊕ a_p。

这告诉我们，对于任何一个非根节点 u，为了让它的值和它父亲的值在一次操作后变得一致，最优的操作就是在 u 的子树上异或 a_u ⊕ a_p。这样操作后，u 和 p 的相对差异就被消除了。

那么根节点 r 呢？ a_r ⊕ c_r = X 所以 c_r = a_r ⊕ X。

现在我们知道了每个节点上需要施加的魔法值 c_v：

  • 如果 v 不是根，c_v = a_v ⊕ a_{parent(v)}。
  • 如果 v 是根 r，c_r = a_r ⊕ X。

总代价就是 Σ size(v) * c_v。 Cost(r, X) = (Σ_{v≠r} size(v) * (a_v ⊕ a_{parent(v)})) + size(r) * (a_r ⊕ X)

我们的目标是最小化这个代价。注意到，求和的第一部分只和根 r 的选择有关，和 X 无关。而第二部分 size(r) * (a_r ⊕ X)，因为 size(r) 就是 n，是正数，所以要让它最小，我们必须让 a_r ⊕ X 最小。一个非负整数的最小值就是 0 啦！所以我们应该选择 X = a_r，这样 c_r 就等于 0，根节点上的操作代价就是 0。

所以，当根为 r 时，最小总代价为： m_r = Σ_{v≠r} size_r(v) * (a_v ⊕ a_{parent_r(v)}) 其中 size_r(v) 和 parent_r(v) 都是在以 r 为根的树下的定义。

换根 DP ​

现在我们有了一个计算 m_r 的公式，但如果对每个 r 都重新建树、计算一次，时间复杂度会是 O(N²)，肯定会超时的，喵。

这时候就要用到我们聪明的“换根DP”技巧了！

  1. 第一次 DFS: 我们先随便选一个根，比如说节点 1。然后做一次 DFS (或者说树形 DP)，计算出以 1 为根时的一些重要信息：

    • sz[u]：以 1 为根时，u 节点子树的大小。
    • dp[u]：以 1 为根时，u 子树内所有节点（不含 u）贡献的代价总和。 dp[u] = Σ_{v 是 u 的孩子} (dp[v] + sz[v] * (a_u ⊕ a_v)) 这样，m_1 就等于 dp[1]。

  2. 第二次 DFS (换根): 现在我们有了 m_1 的值，我们想知道它的邻居 v 作为根时的 m_v 是多少。 假设我们把根从 u 移到它的一个孩子 v。树的结构发生了什么变化呢？

    • 边 (u, v) 的方向反了过来，u 成了 v 的孩子。
    • 原来 v 的子树，现在它的父节点变成了 v 自己，所以 v 的代价贡献项 sz_u(v) * (a_u ⊕ a_v) 消失了。
    • u 成为了 v 的孩子，所以增加了一个 u 的代价贡献项 sz_v(u) * (a_v ⊕ a_u)。
    • sz_u(v) 是以 u 为根时 v 的子树大小，也就是我们第一次 DFS 算出的 sz[v]。
    • sz_v(u) 是以 v 为根时 u 的子树大小。此时 u 的子树是除了原来 v 的子树之外的所有节点，所以大小是 n - sz[v]。

    所以，从 m_u 到 m_v 的递推关系是： m_v = m_u - sz[v] * (a_u ⊕ a_v) + (n - sz[v]) * (a_u ⊕ a_v)m_v = m_u + (n - 2 * sz[v]) * (a_u ⊕ a_v)

    哇！我们得到了一个超级简洁的公式！我们可以用第二次 DFS (或 BFS) 从根 1 出发，根据这个公式计算出所有节点的 m_r 值。

总结一下步骤：

  1. 任选节点 1 为根，进行一次 DFS，计算出所有节点的子树大小 sz[u] 和 m_1 的值。
  2. 从节点 1 开始，进行第二次遍历 (DFS 或 BFS)，利用递推公式 m_v = m_u + (n - 2 * sz[v]) * (a_u ⊕ a_v) 计算出所有 m_r。

就是这样喵！是不是清晰多啦？

代码 ​

这是人家为你准备好的 C++ 代码，里面有详细的注释哦，喵~

cpp
#include <iostream>
#include <vector>
#include <stack>
#include <queue>

using namespace std;
typedef long long ll;

void solve() {
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    if (n == 1) {
        cout << "0\n";
        return;
    }

    // 第一次遍历：以 1 为根，计算子树大小和 m_1
    // 使用栈模拟DFS，确定父子关系和遍历顺序
    vector<int> parent(n + 1, 0);
    vector<int> order;
    stack<int> st;
    st.push(1);
    parent[1] = 0; // 根的父节点设为0
    vector<bool> visited_dfs1(n + 1, false);
    visited_dfs1[1] = true;

    while (!st.empty()) {
        int u = st.top();
        st.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (!visited_dfs1[v]) {
                visited_dfs1[v] = true;
                parent[v] = u;
                st.push(v);
            }
        }
    }

    // 后序遍历计算 sz 和 dp (即 m_1 的组成部分)
    vector<int> sz(n + 1, 0);
    vector<ll> dp(n + 1, 0);
    for (int i = order.size() - 1; i >= 0; i--) {
        int u = order[i];
        sz[u] = 1;
        for (int v : adj[u]) {
            if (v == parent[u]) continue;
            sz[u] += sz[v];
            dp[u] += dp[v] + (a[u] ^ a[v]) * 1LL * sz[v];
        }
    }

    // 第二次遍历：换根DP，计算所有 m_r
    vector<ll> ans(n + 1, 0);
    ans[1] = dp[1]; // m_1
    queue<int> q;
    q.push(1);
    vector<bool> visited_bfs(n + 1, false);
    visited_bfs[1] = true;

    while (!q.empty()) {
        int u = q.front();
        q.pop();

        for (int v : adj[u]) {
            if (!visited_bfs[v]) {
                visited_bfs[v] = true;
                // 从 u 换根到 v
                // sz[v] 是以 1 为根时 v 的子树大小
                ans[v] = ans[u] + (ll)(n - 2 * sz[v]) * (a[u] ^ a[v]);
                q.push(v);
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << (i == n ? "" : " ");
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

知识点介绍 ​

这道题用到了几个在算法竞赛中非常核心的知识点，喵，我们来梳理一下吧！

  1. 位运算 (Bitwise Operations)

    • 异或 (XOR, ⊕): 异或是一个神奇的运算。它的性质 x ⊕ x = 0 和 x ⊕ 0 = x 在这道题的推导中起到了关键作用，帮助我们消去了复杂的项。另外，位运算的各个位之间是相互独立的，这允许我们将一个复杂的问题分解成处理单个二进制位的小问题，虽然这道题我们最终没有按位分解，但这个思想很重要。

  2. 树形动态规划 (Tree DP)

    • 树形DP是一种在树形结构上进行动态规划的方法。通常，DP的状态会定义在节点上，dp[u] 表示在以 u 为根的子树中计算出的某个值。状态的转移则依赖于 u 的孩子们。在我们的第一次DFS中，dp[u] 就存储了 u 子树内的代价和。

  3. 换根DP (Rerooting DP)

    • 这是树形DP的一种特殊技巧，也叫二次扫描法。当题目要求我们计算以每个节点为根时的某个信息时，换根DP就是不二之选。
    • 第一步: 任选一个根（如节点1），通过一次DFS（自底向上）计算出所有子树的信息，以及以节点1为根时的答案。
    • 第二步: 再进行一次DFS（自顶向下），根据父节点已经算好的答案，通过一个快速的状态转移公式，推导出当前节点的答案。这个公式的关键在于分析根从父节点 u 移动到子节点 v 时，答案发生了哪些变化。就像我们推导出的 m_v = m_u + (n - 2 * sz[v]) * (a_u ⊕ a_v) 一样。

掌握了这些，主人在遇到类似的树上问题时，一定会更加得心应手！喵呜~

希望这篇题解能帮到你！如果还有不明白的地方，随时可以再来问我哦，喵~

Released under the MIT License.

Copyright © 2024-present Moe