【蓝桥备赛】异或和——树状数组、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 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);
        }
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/515872.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Three.js——scene场景、几何体位置旋转缩放、正射投影相机、透视投影相机

个人简介 &#x1f440;个人主页&#xff1a; 前端杂货铺 &#x1f64b;‍♂️学习方向&#xff1a; 主攻前端方向&#xff0c;正逐渐往全干发展 &#x1f4c3;个人状态&#xff1a; 研发工程师&#xff0c;现效力于中国工业软件事业 &#x1f680;人生格言&#xff1a; 积跬步…

医院云HIS系统源码,二级医院、专科医院his系统源码,经扩展后能够应用于医联体/医共体

基于云计算技术的B/S架构的HIS系统&#xff0c;为医疗机构提供标准化的、信息化的、可共享的医疗信息管理系统&#xff0c;实现医患事务管理和临床诊疗管理等标准医疗管理信息系统的功能。 系统利用云计算平台的技术优势&#xff0c;建立统一的云HIS、云病历、云LIS&#xff0…

Linux集群部署项目

目录 一&#xff0c;环境准备 1.1.安装MySQL 1.2.安装JDK 1.3.安装TomCat 1.4.安装Nginx 二&#xff0c;部署 2.1.后台服务部署 2.2.Nginx配置负载均衡及静态资源部署 一&#xff0c;环境准备 1.1.安装MySQL 将MySQL的安装包上传至服务器 查看系统中是否存在mariadb&…

167.乐理基础-四个偏音、六声、七声、清雅燕乐

如果到这五线谱还没记住还不认识的话去看102.五线谱-高音谱号与103.五线谱-低音谱号这两个里&#xff0c;这里面有五线谱对应的音名&#xff0c;对比着看 如果不认识调号去看112.五线谱的调号&#xff08;一&#xff09;、113.五线谱的调号&#xff08;二&#xff09;、114.快…

图片改大小尺寸怎么改?几个修改图片尺寸的方法

日常生活和工作中&#xff0c;图片的大小和尺寸对于我们的工作和生活都至关重要&#xff0c;因此我们经常需要调整图片的大小。我们都知道压缩图是一款功能强大的图片在线处理工具&#xff0c;那么用它怎么调整图片大小呢&#xff1f;下面就让我们一起来看一下具体的操作步骤。…

Sora的阅读技术报告

sora的技术报告 走进sorasora的特性sora的介绍sora的实际操作sora的发展安全措施研究技术 走进sora 大家好&#xff0c;我是清风之上。随着人工智能的发展&#xff0c;慢慢的他已经出现在我们生活中的各个角落&#xff0c;其中有API推出的sora&#xff0c;让我们震惊不已&…

应急响应实战笔记05Linux实战篇(2)

第2篇&#xff1a;捕捉短连接 0x00 前言 ​ 短连接&#xff08;short connnection&#xff09;是相对于长连接而言的概念&#xff0c;指的是在数据传送过程中&#xff0c;只在需要发送数据时&#xff0c;才去建立一个连接&#xff0c;数据发送完成后&#xff0c;则断开此连接…

多叉树题目:N 叉树的层序遍历

文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目 标题和出处 标题&#xff1a;N 叉树的层序遍历 出处&#xff1a;429. N 叉树的层序遍历 难度 4 级 题目描述 要求 给定一个 N 叉树的根结点 root \texttt{root} root&#xf…

架构之道:架构、结构、中间件、安全性

对本篇文章中有些此不是很理解的&#xff0c;可以看之前讲解的后端通用技术大全&#xff1a;后端技术大全-CSDN博客 一起食用&#xff0c;效果更加。 一、架构到底是什么 关于架构这个概念很难给出一个明确的定义&#xff0c;也没有一个标准的定义。 硬是要给一个概述&#…

社交媒体市场:揭示Facebook的商业模式

在数字化时代&#xff0c;社交媒体已经成为人们生活中不可或缺的一部分。Facebook作为全球最大的社交媒体平台之一&#xff0c;其商业模式的运作方式对于了解社交媒体市场的发展趋势和影响力至关重要。本文将深入探讨Facebook的商业模式&#xff0c;剖析其运作机制&#xff0c;…

ChatGPT 之百万富翁

原文&#xff1a;The ChatGPT Millionaire 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 介绍 当我写下这些文字时&#xff0c;ChatGPT 已经成为有史以来增长最快的技术平台 - 仅用 5 天就达到了一百万用户。相比之下&#xff0c;Netflix 用了 3 年&#xff0c;Twit…

查询SQL server数据库在后台执行过的语句

查询SQL server数据库在后台执行过的语句 SELECT TOP 30000total_worker_time/1000 AS [总消耗CPU 时间(ms)],execution_count [运行次数],qs.total_worker_time/qs.execution_count/1000 AS [平均消耗CPU 时间(ms)],last_execution_time AS [最后一次执行时间],min_worker_ti…

机器狗首次阵亡!美国警方披露详情

ChatGPT狂飙160天&#xff0c;世界已经不是之前的样子。 新建了免费的人工智能中文站https://ai.weoknow.com 新建了收费的人工智能中文站https://ai.hzytsoft.cn/ 更多资源欢迎关注 那天&#xff0c;唯一的伤亡者是我们的机器狗。 美国警察最新公布一则案件&#xff1a;波士顿…

Spring API 接口和自定义类来实现AOP(Spring学习笔记十)

1、什么是AOP 全称是 Aspect Oriented Programming 即&#xff1a;面向切面编程。是OOP&#xff08;面向对象编程&#xff09;的延续&#xff0c;也是Spring框架中的一个重要内容&#xff0c;是函数式编程的一种衍生泛型。简单的说他就是把我们程序重复的代码抽取出来&#xf…

【C++】引用与指针

​​ &#x1f331;博客主页&#xff1a;青竹雾色间. &#x1f618;博客制作不易欢迎各位&#x1f44d;点赞⭐收藏➕关注 ✨人生如寄&#xff0c;多忧何为 ✨ 目录标题 前言一.引用&#xff08;Reference&#xff09;二.指针&#xff08;Pointer&#xff09;三. 比较与总结 前…

随机生成Long全范围数

随机生成Long全范围数 前言实现思路主要代码分区随机生成过程案例&#xff1a;随机生成100个数 朴素的比较总结 前言 使用自带的Random.nextLong()函数生成Long型的长整数&#xff0c;范围比较小&#xff0c;如下图。100个随机数没看见10以内的数字。所以考虑实现随机化生成大…

新质生产力丨zData X 数据库一体机助力财政一体化平台全面升级

在数字化转型的大潮中&#xff0c;某财政局积极响应国家财政管理现代化的战略部署&#xff0c;启动了财政一体化平台升级改造工程。该项目旨在将财政局内部各部门及其各自独立的业务系统进行全面整合&#xff0c;构建起一个集约化的财政管理平台&#xff0c;力求通过技术创新推…

【剑指offr--C/C++】JZ31 栈的压入、弹出序列

一、题目 二、思路及代码 借助一个辅助栈来模拟入栈过程&#xff0c; ①在入栈之前先判断当前要入栈的元素是否与出栈数组当前元素相同&#xff0c; ② 如果不相同就入栈&#xff1b; ③如果相同就不用入栈了&#xff08;不入栈出栈&#xff09;&#xff0c;然后再依次取出栈的…

Redis中的复制功能(五)

心跳检测 概述 在命令传播阶段&#xff0c;从服务器默认会以每秒一次的频率&#xff0c;向主服务器发送命令: REPLCONF ACK < replication_offset >其中replication_offset是从服务器当前的复制偏移量。 发送REPLCONF ACK命令对于主从服务器有三个作用: 1.检测主从服…

python学习23:python中的列表(list)中的常用方法

列表(list)中的常用方法 1.列表中常用的方法主要有如下的方法&#xff1a; 2.代码演示主要常用的方法 查找某元素在列表内的下标索引&#xff1a;list.index(元素&#xff09; start_list [coco, xuanxuan, taotao] # 1.1 查找某元素在列表内的下标索引 index start_list…