U399207 P3401 洛谷树改

原题链接：[https://www.luogu.com.cn/problem/P3401](https://www.luogu.com.cn/problem/P3401) > # 洛谷树 > > ## 题目背景 > > 萌哒的 Created_equal 小仓鼠种了一棵洛谷树！ > > （题目背景是辣鸡小仓鼠乱写的 QAQ）。 > > ## 题目描述 > > 树是一个无环、联通的无向图，由 $n$ 个点和 $n-1$ 条边构成。树上两个点之间的路径被定义为他们之间的唯一一条简单路径——显然这是一条最短路径。 > > 现在引入一个概念——子路径。假设树上两个点 $p_1$ 和 $p_n$ 之间的路径是 $P = \langle p_1,p_2,p_3, \ldots, p_n \rangle $，那么它的子路径被定义为某一条路径 $P'$，满足 $P'= \langle p_i,p_{i+1},p_{i+2},\ldots,p_j \rangle $，其中 $1\le i \le j \le n$。显然，原路径是一条子路径，任意一个点也可以作为子路径。 > > 我们给每条边赋予一个边权。萌萌哒的 Sugar 问小仓鼠：对于任意两个点 $u$ 和 $v$，你能快速求出，$u$ 到 $v$ 的路径上所有子路径经过的边的边权的 $\text{xor}$ 值的和是多少。具体地说就是，你把 $u$ 到 $v$ 的路径上所有子路径全部提出来，然后分别把每个子路径上经过的边的边权 $\text{xor}$ 在一起，最后求出得到的所有 $\text{xor}$ 值的和。 > > 什么？你不知道 $\text{xor}$？那就去百度啊！ > > 这时候，fjzzq2002 大爷冒了粗来：窝还要你滋磁修改某条边边权的操作！ > > 小仓鼠那么辣鸡，当然不会做这道题啦。于是他就来向你求救！ > > ## 输入格式 > 第一行两个正整数 $n$ 和 $q$，表示点的个数，查询和询问的总次数。 > > 接下来 $n-1$ 行，每行两个正整数 $u,v$ 和一个非负整数 $w$，表示 $u$ 和 $v$ 两个点之间有一条边权为 $w$ 的边。 > > 接下来 $q$ 行，格式为 `1 u v` 或 `2 u v w`。 如果为 `1 u v` 操作，你需要输出 $u$ 到 $v$ 的路径上所有子路径经过的边的边权的 $\text{xor}$ 值的和是多少。 > 如果为 `2 u v w` 操作，你需要把 $u$ 到 $v$ 这条边的边权改为 $w$，保证这条边存在。 > > ## 输出格式 > > 对于每个 $1$ 操作，输出答案。 > > ## 样例 #1 > > ### 样例输入 #1 > > ``` > 5 3 > 1 2 3 > 2 3 3 > 2 4 6 > 4 5 1 > 1 3 4 > 2 2 4 7 > 1 3 5 > ``` > > ### 样例输出 #1 > > ``` > 14 > 26 > ``` > > ## 提示 > > |测试点编号|$n=$|$q=$|备注| > |:-:|:-:|:-:|:-:| > |$1$|$100$|$5$|无| > |$2$|$100$|$20$|无| > |$3$|$100$|$100$|无| > |$4$|$5\times 10^3$|$10^3$|无| > |$5$|$5\times 10^3$|$2\times 10^3$|无| > |$6$|$5\times 10^3$|$3\times 10^3$|无| > |$7$|$10^4$|$10^4$|第 $i$ 条边连接第 $i$ 个点和第 $i+1$ 个点，且没有 $2$ 操作| > |$8$|$10^4$|$2\times 10^4$|第 $i$ 条边连接第 $i$ 个点和第 $i+1$ 个点，且没有 $2$ 操作| > |$9$|$10^4$|$10^4$|第 $i$ 条边连接第 $i$ 个点和第 $i+1$ 个点| > |$10$|$10^4$|$2\times 10^4$|第 $i$ 条边连接第 $i$ 个点和第 $i+1$ 个点| > |$11$|$10^4$|$10^4$|没有 $2$ 操作| > |$12$|$10^4$|$2\times 10^4$|没有 $2$ 操作| > |$13$|$2\times 10^4$|$2\times 10^4$|没有 $2$ 操作| > |$14$|$3\times 10^4$|$3\times 10^4$|没有 $2$ 操作| > |$15$|$3\times 10^4$|$10^4$|无| > |$16$|$2\times 10^4$|$2\times 10^4$|无| > |$17$|$2\times 10^4$|$2\times 10^4$|无| > |$18$|$3\times 10^4$|$2\times 10^4$|无| > |$19$|$2\times 10^4$|$3\times 10^4$|无| > |$20$|$3\times 10^4$|$3\times 10^4$|无| > > 对于 $100\%$ 的数据，所有边权小于等于 $1023$。

给定$n,q(1 \le n,q \le 10^5)$及长度为$n$的序列，支持单点修改，查询一个区间的**所有子区间的异或和**的总和。序列的元素均小于$1000$。

第一行n,q 第二行n个数表示序列 接下来q行，每行三个数，第一个数op=1表示修改，后面两个数x,k表示将x修改为k，op=2表示查询，后面两个数表示l,r

如题目描述

如题目描述