题目传送门
题意：
给出一颗 个结点的树，第
个结点的权值为
。
定义点 到点
的路径的长度为点
到点
的最短路径上的所有结点的权值的异或和。
单独一个点不算做路径。
现在要求你维护 个操作：
总共有两种操作，一种是把某一个点的权值 改成
，另一种是询问点
到点
之间的所有子路径的长度的异或和。
注意：子路径。
数据范围：
题解：
很明显你要掏出树剖板子，点修改区间求和线段树板子。
然后会发现一些规律，路径上的任意点 ，
被异或的次数是
，
是路径长度。
那么 有贡献必须
是奇数。
当 是偶数时，是可以的。
当 是偶数是可以的。
所以当 是偶数的时候，答案是路径长度的异或和。
当 是奇数的时候，答案是路径长度的异或和 异或 下标为奇数的异或和。
线段树维护区间异或和，区间内下标为奇数的异或和。
说的下标为奇数都是相对于区间而言的。
感受：
过了之后去百度搜了搜别人过了的代码，想知道有没有更简便的做法。
结果就是别人的代码长度比我的二分之一还要少。
我好菜啊。
这个真的是裸题吗，我线段树魔改了好久，还对拍了一会才过题。
这份代码用了快读比不用慢，不知道为什么。
代码：
#include<bits/stdc++.h>
using namespace std ;
typedef unsigned long long ull ;
const int maxn = 2e5 + 5 ;
int n , q ;
int num , head[maxn] ;
int w[maxn] , wt[maxn] , son[maxn] , dfn[maxn] , fa[maxn] ;
int cnt = 0 ;
int dep[maxn] , siz[maxn] , top[maxn] ;
int sum[maxn << 2] , sum1[maxn << 2] ;
struct Edge
{
int v , next ;
} edge[maxn << 1] ;
void add_edge(int u , int v)
{
edge[num].v = v ;
edge[num].next = head[u] ;
head[u] = num ++ ;
}
int read()
{
int x=0;
char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar();
return x;
}
void dfs1(int x , int f , int deep)
{
dep[x] = deep ;
fa[x] = f ;
siz[x] = 1 ;
son[x] = 0 ;
int maxson = -1 ;
for(int i = head[x] ; i != -1 ; i = edge[i].next)
{
int y = edge[i].v ;
if(y == f) continue ;
dfs1(y , x , deep + 1) ;
siz[x] += siz[y] ;
if(siz[y] > maxson)
son[x] = y , maxson = siz[y] ;
}
}
void dfs2(int x , int topf)
{
dfn[x] = ++ cnt ;
wt[cnt] = w[x] ;
top[x] = topf ;
if(!son[x]) return ;
dfs2(son[x] , topf) ;
for(int i = head[x] ; i != -1 ; i = edge[i].next)
{
int y = edge[i].v ;
if(y == fa[x] || y == son[x]) continue ;
dfs2(y , y) ;
}
}
int ls(int x)
{
return x << 1 ;
}
int rs(int x)
{
return x << 1 | 1 ;
}
void build(int id , int l , int r)
{
if(l == r){sum1[id] = sum[id] = wt[l] ; return ;}
int mid = (l + r) >> 1 ;
int len = mid - l + 1 ;
build(ls(id) , l , mid) ;
build(rs(id) , mid + 1 , r) ;
sum[id] = sum[ls(id)] ^ sum[rs(id)] ;
sum1[id] = sum1[ls(id)] ;
if(len % 2 == 0) sum1[id] ^= sum1[rs(id)] ;
else sum1[id] ^= (sum[rs(id)] ^ sum1[rs(id)]) ;
}
void update(int id , int l , int r , int x , int y)
{
int mid = (l + r) / 2 ;
int len = mid - l + 1 ;
if(l == r && l == x){sum1[id] = sum[id] = y ; return ;}
if(x <= mid) update(ls(id) , l , mid , x , y) ;
else update(rs(id) , mid + 1 , r , x , y) ;
sum[id] = sum[ls(id)] ^ sum[rs(id)] ;
sum1[id] = sum1[ls(id)] ;
if(len % 2 == 0) sum1[id] ^= sum1[rs(id)] ;
else sum1[id] ^= (sum[rs(id)] ^ sum1[rs(id)]) ;
}
int query(int id , int l , int r , int x , int y)
{
int ans = 0 ;
int mid = (l + r) / 2 ;
if(x <= l && r <= y) return sum[id] ;
if(x <= mid) ans ^= query(ls(id) , l , mid , x , y) ;
if(y > mid) ans ^= query(rs(id) , mid + 1 , r , x , y) ;
return ans ;
}
int query1(int id , int l , int r , int x , int y , int f)
{
int ans = 0 ;
int mid = (l + r) / 2 ;
if(x <= l && r <= y)
{
if(f == (l - x + 1) % 2) return sum1[id] ;
else return sum[id] ^ sum1[id] ;
}
if(x <= mid) ans ^= query1(ls(id) , l , mid , x , y , f) ;
if(y > mid) ans ^= query1(rs(id) , mid + 1 , r , x , y , f) ;
return ans ;
}
void upd_range(int x , int k)
{
update(1 , 1 , n , dfn[x] , k) ;
}
int cal1(int x , int y)
{
int ans = 0 ;
while(top[x] != top[y])
{
if(dep[top[x]] < dep[top[y]]) swap(x , y) ;
ans ^= query(1 , 1 , n , dfn[top[x]] , dfn[x]) ;
x = fa[top[x]] ;
}
if(dep[x] > dep[y]) swap(x , y) ;
ans ^= query(1 , 1 , n , dfn[x] , dfn[y]) ;
return ans ;
}
int cal2(int x , int y)
{
int ans = 0 ;
bool fx = 1 , gx ;
bool fy , gy = 1 ;
while(top[x] != top[y])
{
if(dep[top[x]] >= dep[top[y]])
{
int len = dep[x] - dep[top[x]] + 1 ;
if(len % 2 == 0) gx = !fx , fx = !gx ;
else gx = fx , fx = !gx ;
ans ^= query1(1 , 1 , n , dfn[top[x]] , dfn[x] , gx) ;
x = fa[top[x]] ;
}
else
{
int len = dep[y] - dep[top[y]] + 1 ;
if(len % 2 == 0) fy = !gy , gy = !fy ;
else fy = gy , gy = !fy ;
ans ^= query1(1 , 1 , n , dfn[top[y]] , dfn[y] , fy) ;
y = fa[top[y]] ;
}
}
if(dep[x] < dep[y])
ans ^= query1(1 , 1 , n , dfn[x] , dfn[y] , fx) ;
else
ans ^= query1(1 , 1 , n , dfn[y] , dfn[x] , gy) ;
return ans ;
}
int lca(int x, int y)
{
while(top[x] != top[y])
{
if(dep[top[x]] < dep[top[y]]) swap(x , y) ;
x = fa[top[x]] ;
}
return dep[x] < dep[y] ? x : y ;
}
int q_range(int x , int y)
{
int ans = 0 ;
int z = lca(x , y) ;
int len = dep[x] + dep[y] - 2 * dep[z] + 1 ;
ans ^= cal1(x , y) ;
if(len % 2 == 1) ans ^= cal2(x , y) ;
return ans ;
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("A.out","w",stdout);
scanf("%d%d" , &n , &q) ;
num = 0 ;
memset(head , -1 , sizeof(head)) ;
for(int i = 1 ; i <= n ; i ++) scanf("%d" , &w[i]) ;
for(int i = 1 ; i <= n - 1 ; i ++)
{
int u , v ;
scanf("%d%d" , &u , &v) ;
add_edge(u , v) ;
add_edge(v , u) ;
}
dfs1(1 , 0 , 1) ;
dfs2(1 , 1) ;
build(1 , 1 , n) ;
vector<int> h ;
while(q --)
{
int op , a , b ;
scanf("%d%d%d" , &op , &a , &b) ;
if(op == 1) upd_range(a , b) ;
else printf("%d\n" , q_range(a , b)) ;
}
return 0 ;
}