题目链接
异或和
思路分析
树上每个点都有一个点权,对树上的更新操作是修改指定点的点权,查询操作是查询指定点为根结点的子树点权异或和。
这里的这些操作都和树状数组的单点修改和区间查询非常相似,即我们在修改一个点时,同时修改其往上所有祖先的子树点权异或和,这样在查询操作时可以直接打印出结果。
然而,我们一开始并不知道该结点的父节点到底到底是哪一个,所以我们可以通过一个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 block
e.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);
}
}
}