結果

問題 No.1641 Tree Xor Query
コンテスト
ユーザー roaris
提出日時 2021-08-06 21:51:58
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 204 ms / 5,000 ms
コード長 1,098 bytes
コンパイル時間 4,369 ms
コンパイル使用メモリ 252,196 KB
最終ジャッジ日時 2025-01-23 15:08:48
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define rep(i, n) for (int i=0; i<n; i++)
#define pb push_back
typedef long long ll;

int N, Q;
int C[100010];
vector<int> G[100010];
vector<int> tour;
int s[100010];
int t[100010];
int c = 0;

void euler(int v, int pv) {
    s[v] = c++;
    tour.pb(v);
    for (int nv:G[v]) {
        if (nv==pv) continue;
        euler(nv, v);
    }
    t[v] = c;
}

int op(int x, int y) { return x^y;}
int e() {return 0;}

int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    
    cin >> N >> Q;
    rep(i, N) cin >> C[i];
    rep(i, N-1) {
        int a, b; cin >> a >> b;
        G[a-1].pb(b-1);
        G[b-1].pb(a-1);
    }
    euler(0, -1);
    
    segtree<int, op, e> st(N);
    rep(i, N) st.set(i, C[tour[i]]);
    
    int idx[N];
    rep(i, N) idx[tour[i]] = i;
    
    while (Q--) {
        int T, x, y; cin >> T >> x >> y;
        if (T==1) {
            st.set(idx[x-1], C[x-1]^y);
            C[x-1] ^= y;
        } else {
            cout << st.prod(s[x-1], t[x-1]) << endl;
        }
    }
}
0