【蓝桥备赛】异或和——树状数组、DFS

题目链接

异或和

思路分析

树上每个点都有一个点权，对树上的更新操作是修改指定点的点权，查询操作是查询指定点为根结点的子树点权异或和。
这里的这些操作都和树状数组的单点修改和区间查询非常相似，即我们在修改一个点时，同时修改其往上所有祖先的子树点权异或和，这样在查询操作时可以直接打印出结果。
然而，我们一开始并不知道该结点的父节点到底到底是哪一个，所以我们可以通过一个dfs去预处理。

当然，此题也可以比较暴力的去处理，此处就不进行列举了。

参考代码

在这里插入图片描述

Java

import java.io.*;
import java.util.Vector;public class Main {static int n, m;static int[] arr, fa, dp;static Vector<Vector<Integer>> edge;static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));// 通过 dfs 先求出初始状态下以每个结点为根的子树点权异或和// 记录下他的父亲结点，方便后续更新该结点时,同时更新其父亲结点static void dfs(int x, int f) {fa[x] = f;dp[x] ^= arr[x];for(int to : edge.get(x)) {if(to == f) continue;dfs(to, x);dp[x] ^= dp[to];}}static void modify(int x, int y) {int t = arr[x]; // 记录下当前结点的初始值arr[x] = y; // 修改当前点权while(x != -1) {dp[x] = dp[x] ^ t ^ y;// 根据 a^a=0的特性，删除旧的点权x = fa[x];// 向上修改父亲结点}}static void search(int x) {out.println(dp[x]); // 直接打印即可}public static void main(String[] args) {Scanner sc = new Scanner();n = sc.nextInt();m = sc.nextInt();arr = new int[n + 1];fa = new int[n + 1];dp = new int[n + 1];for(int i = 1; i <= n; ++i) {arr[i] = sc.nextInt();}edge = new Vector<>();for(int i = 0; i <= n; ++i) {edge.add(new Vector<>());}for(int i = 1; i <= n - 1; ++i) {int u = sc.nextInt();int v = sc.nextInt();edge.get(u).add(v);edge.get(v).add(u);}dfs(1, -1);for(int i = 1; i <= m; ++i) {int op = sc.nextInt();if(op == 1) {int x = sc.nextInt();int y = sc.nextInt();modify(x, y);}if(op == 2) {int x = sc.nextInt();search(x);}}out.flush();}
}
class Scanner {static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));public int nextInt() {try {st.nextToken();} catch (IOException e) {// TODO Auto-generated catch blocke.printStackTrace();}return (int)st.nval;}
}

C/C++

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;int n, m, arr[N], fa[N], dp[N];
vector<int> edge[N];
// 标记父节点并初始化
void dfs(int x, int f)
{fa[x] = f;dp[x] ^= arr[x];for(int to : edge[x]){if(to == f) continue;dfs(to, x);dp[x] ^= dp[to];}
}
// 修改当前点点权,并更新与其关联的父节点
void update(int x, int y)
{int t = arr[x];arr[x] = y;while(x != -1){dp[x] = dp[x] ^ t ^ y;x = fa[x];}
}
// 查询
void query(int x)
{cout << dp[x] << "\n";
}int main()
{ios::sync_with_stdio(0), cin.tie(0);cin >> n >> m;for (int i = 1; i <= n; ++i) cin >> arr[i]; // 记录点权for(int i = 1; i <= n - 1; ++i){int u, v;cin >> u >> v;edge[u].push_back(v);edge[v].push_back(u);}dfs(1, -1);while(m--){int op; cin >> op;if(op==1){int x, y; cin >> x >> y;update(x, y);}else{int x; cin >> x;query(x);}}
}