Untitled

mail@pastecode.io avatar
unknown
plain_text
a month ago
5.1 kB
7
Indexable
Never
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
template<class T> using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define ll long long
#define db double
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define speed ios_base::sync_with_stdio(false);cin.tie(0), cout.tie(0);
/*
                    " وَأَن لَّيْسَ لِلْإِنسَانِ إِلَّا مَا سَعَى ﴿39﴾ وَأَنَّ سَعْيَهُ سَوْفَ يُرَى ﴿40﴾ ثُمَّ يُجْزَاهُ الْجَزَاء الْأَوْفَى "
*/
const ll N = 2e5 + 5, inf = 2e18, mod = 1e9 + 7;
ll dx[] = {0, 0, -1, 1, -1, 1, 1, -1};
ll dy[] = {1, -1, 0, 0, 1, 1, -1, -1};
char di[] = {'R', 'L', 'U', 'D'};
int tin[N], tout[N], timer, up[N][22];

struct segtree {
    ll tree_size;
    vector<ll> segdata;

    segtree(ll n) {
        tree_size = 1;
        while (tree_size < n)
            tree_size *= 2;
        segdata.assign(2 * tree_size, 0);
    }

    void init(vector<ll> &a, ll ni, ll lx, ll rx) {
        if (rx - lx == 1) {
            if (lx < a.size())
                segdata[ni] = a[lx];
            return;
        }
        ll m = (lx + rx) / 2;
        init(a, 2 * ni + 1, lx, m);
        init(a, 2 * ni + 2, m, rx);
        segdata[ni] = megre(segdata[2 * ni + 1], segdata[2 * ni + 2]);
    }

    void init(vector<ll> &a) {
        init(a, 0, 0, tree_size);
    }

    ll megre(ll &l, ll &r) {
        return (l ^ r);
    }

    void set(ll idx, ll val, ll ni, ll lx, ll rx) {
        if (rx - lx == 1) {
            segdata[ni] = val;
            return;
        }
        ll mid = (rx + lx) / 2;
        if (idx < mid)
            set(idx, val, 2 * ni + 1, lx, mid);
        else set(idx, val, 2 * ni + 2, mid, rx);
        segdata[ni] = megre(segdata[2 * ni + 1], segdata[2 * ni + 2]);
    }

    void set(ll idx, ll val) {
        set(idx, val, 0, 0, tree_size);
    }

    ll get(ll l, ll r, ll ni, ll lx, ll rx) {
        if (lx >= l and rx <= r)
            return segdata[ni];
        if (lx >= r or rx <= l)
            return 0;
        ll mid = (rx + lx) / 2;
        ll lf = get(l, r, 2 * ni + 1, lx, mid);
        ll ri = get(l, r, 2 * ni + 2, mid, rx);
        return megre(lf, ri);
    }

    ll get(ll l, ll r) {
        return get(l, r, 0, 0, tree_size);
    }
};

vector<ll> adj[N], parent(N), depth(N);
vector<ll> euler, val;

void dfs(int u, int p, int d = 0) {
    parent[u] = p;
    depth[u] = d;
    tin[u] = timer++;
    euler.push_back(val[u]);
    for (auto v: adj[u]) {
        if (v != p)
            dfs(v, u, d + 1);
    }
    tout[u] = timer++;
    euler.push_back(val[u]);
}

ll n, q;

void pre() {
    for (int i = 0; i < 22; ++i) {
        for (int u = 1; u <= n; ++u) {
            if (!i)
                up[u][i] = parent[u];
            else
                up[u][i] = up[up[u][i - 1]][i - 1];
        }
    }
}

int binleft(ll node, int u) {
    for (int b = 0; b < 22; ++b) {
        if (u & (1 << b))
            node = up[node][b];
    }
    return node;
}

int lca(int a, int b) {
    if (depth[a] < depth[b])
        swap(a, b);
    a = binleft(a, depth[a] - depth[b]);
    if (a == b)
        return a;
    for (int bit = 21; bit >= 0; bit--) {
        if (up[a][bit] == up[b][bit])
            continue;
        a = up[a][bit];
        b = up[b][bit];
    }
    return up[a][0];
}

void solve() {
    cin >> n >> q;

    for (int i = 0; i < n; ++i) {
        ll x;
        cin >> x;
        val.push_back(x);
    }
    for (int i = 0; i < n - 1; ++i) {
        ll a, b;
        cin >> a >> b;
        a--, b--;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    dfs(0, -1);
    pre();
    segtree st(euler.size());
    st.init(euler);
    while (q--) {
        ll type;
        cin >> type;
        if (type == 1) {
            ll node, x;
            cin >> node >> x;
            node--;
            st.set(tin[node], x);
            st.set(tout[node], x);
            val[node] = x;
        } else {

            ll u, v;
            cin >> u >> v;
            u--, v--;
//            cerr << lca(u, v) << "\n";
            ll x = st.get(tin[lca(u, v)], tout[u]);
            ll y = st.get(tin[lca(u, v)], tout[v]);
            ll z = val[lca(u, v)];
            cout << (x ^ y ^ z) << "\n";
        }
    }
}

void file() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
}

int main() {
    speed
//    file();
    freopen("cowland.in", "r", stdin);
    freopen("cowland.out", "w", stdout);
    int testcases = 1;
//    cin >> testcases;
    while (testcases--)
        solve();

}
Leave a Comment