C++(g++ 7.5.0) 解法, 执行用时: 565ms, 内存消耗: 118908K, 提交时间: 2023-07-10 18:49:39

#include <iostream>
#include <cstring>
#include <vector>

#define int long long

using namespace std;

const int N = 1000010;

int n, m, a[N];
vector<int> adj[N];
int l[N], r[N], fa[N], ts, ts0;
int st[N * 2][20], lg[N * 2];
int first[N], dep[N];

void dfs(int u, int father) {
  fa[u] = father; 
  l[u] = ++ts;
  st[++ts0][0] = u, first[u] = ts0;
  dep[u] = dep[father] + 1;
  for (auto v : adj[u]) {
    if (v == father) continue;
    dfs(v, u);
    st[++ts0][0] = u;
  }
  r[u] = ts;
}

int mind(int x, int y) {
  return dep[x] < dep[y] ? x : y;
}
 
int lca(int u, int v) {
  int l = first[u], r = first[v]; 
  if (l > r) swap(l, r);
  int k = lg[r - l + 1];
  return mind(st[l][k], st[r - (1 << k) + 1][k]); 
}

void init() {
  lg[1] = 0;
  for (int i = 2; i <= ts0; i++) lg[i] = lg[i >> 1] + 1;
  for (int j = 1; j < 20; j++)
    for (int i = 1; i + (1 << j) - 1 <= ts0; i++)
      st[i][j] = mind(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}

struct Fenw {
  int tr[N];
  
  int lowbit(int x) {
    return x & -x;
  }
   
  void add(int x, int v) {
    for (; x <= ts; x += lowbit(x))
      tr[x] ^= v;
  }
  
  void add(int l, int r, int x) {
    add(l, x), add(++r, x);
  }
  
  int ask(int x) {
    int res = 0;
    for (; x; x -= lowbit(x))
      res ^= tr[x];
    return res;
  }
  
} t[2];

signed main() {
  cin.tie(0)->sync_with_stdio(false);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i < n; i++) {
    int u, v;
    cin >> u >> v;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }
  dfs(1, 0);
  init();
  for (int i = 1; i <= n; i++) {
    t[dep[i] & 1].add(l[i], r[i], a[i]);
  }
  while (m--) {
    int op, u, v;
    cin >> op >> u >> v;
    if (op == 1) {
      t[dep[u] & 1].add(l[u], r[u], a[u] ^ v);
      a[u] = v;
    } else {
      int p = lca(u, v);
      int dist = dep[u] + dep[v] - dep[p] - dep[fa[p]], res = 0;
      if (dist & 1) {
        res ^= t[!(dep[u] & 1)].ask(l[u]) ^ t[!(dep[u] & 1)].ask(l[fa[p]]);
        res ^= t[!(dep[v] & 1)].ask(l[v]) ^ t[!(dep[v] & 1)].ask(l[p]);
      } else {
        for (int i : {0, 1}) {
          res ^= t[i].ask(l[u]) ^ t[i].ask(l[fa[p]]);
          res ^= t[i].ask(l[v]) ^ t[i].ask(l[p]);
        }
      }
      cout << res << '\n';
    }
  }
  return 0;
}

C++14(g++5.4) 解法, 执行用时: 406ms, 内存消耗: 35700K, 提交时间: 2020-03-26 18:28:56

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
#define fi first
#define se second
#define pb push_back
int n,m,a[N],sz[N],df[N],to[N],son[N],fa[N],cnt,dep[N];
vector<int>v[N];
void dfs1(int o,int pre){
  int s=-1;sz[o]=1;fa[o]=pre;dep[o]=dep[pre]+1;
  for(auto k:v[o]){
    if(k!=pre){
      dfs1(k,o);
      sz[o]+=sz[k];
      if(sz[k]>s){
        s=sz[k];son[o]=k;
      }
    }
  }
}
void dfs2(int o,int t){
  to[o]=t;
  df[o]=++cnt;
  if(son[o])dfs2(son[o],t);
  for(auto k:v[o]){
    if(k==fa[o]||k==son[o])
      continue;
    dfs2(k,k);
  }
}
int T[3][N];
void add(int p,int d,int x){
  for(;p<N;p+=p&-p)T[x][p]^=d;
}
int get(int p,int x){
  int res=0;
  for(;p;p-=p&-p)res^=T[x][p];
  return res;
}
int main() {
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)scanf("%d",a+i);
  for(int i=1;i<n;i++){
    int s,t;
    scanf("%d%d",&s,&t);
    v[s].pb(t);
    v[t].pb(s);
  }
  dfs1(1,0);
  dfs2(1,1);
  for(int i=1;i<=n;i++){
    add(df[i],a[i],dep[i]%2);
    add(df[i],a[i],2);
  }
  for(int i=1;i<=m;i++){
    int ope,l,r;
    scanf("%d",&ope);
    if(ope==1){
      scanf("%d%d",&l,&r);
      add(df[l],a[l]^r,dep[l]%2);
      add(df[l],a[l]^r,2);
      a[l]=r;
    }else{
      scanf("%d%d",&l,&r);
      int sta;
      if(dep[l]%2!=dep[r]%2)sta=2;
      else{
        if(dep[l]&1)sta=0;
        else sta=1;
      }
      int ans=0;
      while(to[l]!=to[r]){
        if(df[l]<df[r])swap(l,r);
        ans^=get(df[to[l]]-1,sta)^get(df[l],sta);
        l=fa[to[l]];
      }
      if(df[l]<df[r])swap(l,r);
      ans^=get(df[r]-1,sta)^get(df[l],sta);
      printf("%d\n",ans);
    }
  }
  return 0;
}