Untitled
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