题解

题面描述
在一棵以节点 $1$ 为根的树上，共有 $n$ 个节点，每个节点 $i$ 初始权值为 $a_i$。小红可以进行如下操作：

• 选择任意节点 $v$ 和一个非负整数 $x$，
• 对节点 $v$ 的子树中所有与 $v$ 的距离为偶数的节点 $u$，执行$$a_u \gets a_u \oplus x\,$$
• 操作的代价为 $x$。

问：最少需要多少总代价，才能将所有节点的权值都变为 $0$？

思路

1. 对树做一次 DFS，以根节点 $1$ 为起点，记录当前节点深度 $d$。
2. 维护两个累积异或值数组
   • $cum[0]$：表示到当前节点为止，对所有深度为偶数位置所做操作的累积异或
   • $cum[1]$：表示到当前节点为止，对所有深度为奇数位置所做操作的累积异或
3. 访问节点 $u$ 时：
   • 设 $pp = d \bmod 2$
   • 当前节点真实权值为 $a_u \oplus cum[pp]$，记作 $v_u$
   • 为了将其变为 $0$，需在此节点施加操作 $x = v_u$，并累加代价 $res \mathrel{+}= x$
   • 同时更新 $cum[pp] \gets cum[pp] \oplus x$
4. 继续 DFS 遍历子节点，完成后回溯时需将本次对 $cum[pp]$ 的修改撤销。

此法对每个节点只做常数次操作，总时间复杂度 $O(n)$。

代码分析

• 使用显式栈模拟递归，避免递归深度过深。
• 每个栈元素包含：节点编号 $u$、父节点 $p$、深度 $d$、阶段标记 $stg$（入栈前处理或回溯处理）、本次操作值 $x$。
• 入栈阶段（$stg=0$）计算需操作值 $x$ 并更新累积异或，出栈阶段（$stg=1$）撤销更新。

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

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

    ll res = 0;               // 最终总代价
    ll cum[2] = {0, 0};       // cum[0] 偶深度异或累积, cum[1] 奇深度异或累积

    struct Node {
        int u, p, d, stg;
        ll x;
    };
    vector<Node> stk;
    stk.reserve(2*n);
    stk.push_back({1, 0, 0, 0, 0});  // 从根节点入栈，深度0，阶段0

    while(!stk.empty()){
        auto cur = stk.back(); stk.pop_back();
        int u = cur.u, p = cur.p, d = cur.d, stg = cur.stg;
        ll x = cur.x;
        if(stg == 0){
            int pp = d & 1;
            // 计算当前真实值，需要补异或到0的值
            ll need = cum[pp] ^ a[u];
            res += need;
            cum[pp] ^= need;  // 更新累积异或
            // 先入回溯阶段，再入子节点
            stk.push_back({u, p, d, 1, need});
            for(int v : g[u]){
                if(v == p) continue;
                stk.push_back({v, u, d+1, 0, 0});
            }
        } else {
            // 回溯时撤销本节点对 cum 的修改
            int pp = d & 1;
            cum[pp] ^= x;
        }
    }

    cout << res;
    return 0;
}

Python

import sys
sys.setrecursionlimit(10**7)

def solve():
    n = int(sys.stdin.readline())
    a = [0] + list(map(int, sys.stdin.readline().split()))
    g = [[] for _ in range(n+1)]
    for _ in range(n-1):
        u, v = map(int, sys.stdin.readline().split())
        g[u].append(v)
        g[v].append(u)

    res = 0
    cum = [0, 0]  # cum[0] 偶深度异或累积, cum[1] 奇深度异或累积

    # 栈元素： (u, parent, depth, stage, x)
    stk = [(1, 0, 0, 0, 0)]
    while stk:
        u, p, d, stage, x = stk.pop()
        if stage == 0:
            pp = d & 1
            # 计算需要异或的值
            need = cum[pp] ^ a[u]
            res += need
            cum[pp] ^= need
            # 回溯阶段
            stk.append((u, p, d, 1, need))
            for v in g[u]:
                if v != p:
                    stk.append((v, u, d+1, 0, 0))
        else:
            # 撤销
            pp = d & 1
            cum[pp] ^= x

    print(res)

if __name__ == "__main__":
    solve()

Java

import java.io.*;
import java.util.*;

public class Main {
    static int n;
    static long[] a;
    static List<Integer>[] g;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(in.readLine());
        a = new long[n+1];
        StringTokenizer st = new StringTokenizer(in.readLine());
        for(int i = 1; i <= n; i++) {
            a[i] = Long.parseLong(st.nextToken());
        }
        g = new ArrayList[n+1];
        for(int i = 1; i <= n; i++) {
            g[i] = new ArrayList<>();
        }
        for(int i = 0; i < n-1; i++) {
            st = new StringTokenizer(in.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            g[u].add(v);
            g[v].add(u);
        }

        long res = 0;
        long[] cum = new long[2]; // cum[0] 偶深度, cum[1] 奇深度

        // 栈元素：u, parent, depth, stage, x
        Deque<long[]> stk = new ArrayDeque<>();
        stk.push(new long[]{1, 0, 0, 0, 0});

        while(!stk.isEmpty()) {
            long[] cur = stk.pop();
            int u = (int)cur[0], p = (int)cur[1], d = (int)cur[2];
            int stage = (int)cur[3];
            long x = cur[4];
            if(stage == 0) {
                int pp = d & 1;
                long need = cum[pp] ^ a[u];
                res += need;
                cum[pp] ^= need;
                // 回溯阶段
                stk.push(new long[]{u, p, d, 1, need});
                for(int v : g[u]) {
                    if(v == p) continue;
                    stk.push(new long[]{v, u, d+1, 0, 0});
                }
            } else {
                int pp = d & 1;
                cum[pp] ^= x; // 撤销
            }
        }

        System.out.println(res);
    }
}

题目内容

在神秘莫测的比特王国中，流传着这样一个传说—在王国深处生长着一棵蕴含天机的神奇大树。这棵树由$n$个节点构成,$1$号点是根节点，

每个节点都记录着一段古老的符文，初始每个节点的符文为$a_i$。传说只有将树上所有节点的符文调和为零，才能开启通往失落宝藏的大门，聪明勇敢的小红接受了挑战，她掌握了一套奇特的操作法则，能够对树中部分节点施法改变其符文，但每次施法都需要付出一定代价,

具体来说，小红可以进行如下操作:

• 选择树中的任一节点$v$及一个非负整数$x$。
• 将$v$ 以及$v$的子树中所有与$v$距离为偶数的节点的权值进行异或操作，即更新为:$a[u]=a[u]\oplus x$
• 每进行一次此操作就产生的代价。

请问小红至少需要花费多少总代价，才能使得所有节点的符文权值均变为$0$?

名词解释

在一棵树中,对于任一节点$v$，以$v$为根节点并包含所有从出发可以达到的后代节点(包括$v$自身)的集合构成了$v$的子树。

在树中，任意两个节点之间仅存在一条简单路径，该路径上所经过的边的数目定义为这两个节点之间的距离。

输入描述

第一行包含一个整数$n$，表示节点的数量.

第二行包含$n$个整数$a_1,a_2,...an$，表示各节点的初始权值。

接下来$n-1$行,每行包含两个整数$u$和$v$，表示树中一你边。所始边构成一棵以$1$为根的树。

$1≤n≤2×10^5$

$0≦a≦10^9$

输出描述

输出一个整数，表示将所有节点的权值变为$0$所需的最小总代价.

样例1

输入

5
1 4 3 5 5
1 2
2 3
3 4
3 5

输出

9

说明

先选择节点$1$，花费$1$的代价进行操作，操作后节点权值变为$[0,4,2,5,5]$

再选择节点$2$，花费$4$的代价进行操作，操作后节点权值变为$[0,0,2,1,1]$

再选择节点$3$，花费$2$的代价进行操作，操作后节点权值变为$[0,0,0,1,1]$

再选择节点$4$，花费$1$的代价进行操作，操作后节点权值变为$[0,0,0,0,1]$

最后选择节点$5$，花费$1$的代价进行操作，操作后节点权值变为$[0,0,0,0,0]$

总花费为$1+4+2+1+1=9$