結果
| 問題 | No.1641 Tree Xor Query |
| ユーザー |
 nonon
|
| 提出日時 | 2024-09-27 11:41:57 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 102 ms / 5,000 ms |
| コード長 | 7,033 bytes |
| コンパイル時間 | 3,778 ms |
| コンパイル使用メモリ | 266,576 KB |
| 実行使用メモリ | 33,152 KB |
| 最終ジャッジ日時 | 2024-09-27 11:42:25 |
| 合計ジャッジ時間 | 5,130 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 18 |
ソースコード
#include <bits/stdc++.h>using namespace std;template <typename Monoid>struct segtree {using S = typename Monoid::S;segtree() : segtree(0) {}segtree(int _n) : segtree(vector<S>(_n, Monoid::e())) {}segtree(const vector<S> &v) : n(v.size()) {log = 1;while ((1 << log) < n) log++;sz = 1 << log;d = vector<S>(2 * sz, Monoid::e());for (int i = 0; i < n; i++) d[i + sz] = v[i];for (int i = sz - 1; i >= 1; i--) update(i);}void set(int p, const S &x) {assert(0 <= p && p < n);p += sz;d[p] = x;for (int i = 1; i <= log; i++) update(p >> i);}S get(int p) const {assert(0 <= p && p < n);return d[p + sz];}S prod(int l, int r) const {assert(0 <= l && l <= r && r <= n);l += sz;r += sz;S pl = Monoid::e(), pr = Monoid::e();while (l < r) {if (l & 1) pl = Monoid::op(pl, d[l++]);if (r & 1) pr = Monoid::op(d[--r], pr);l >>= 1;r >>= 1;}return Monoid::op(pl, pr);}S all_prod() const { return d[1]; }private:int n, log, sz;vector<S> d;void update(int p) {d[p] = Monoid::op(d[2 * p], d[2 * p + 1]);}};template<typename Monoid>struct heavy_light_decomposition {using S = typename Monoid::S;heavy_light_decomposition(int _n, bool _e, int _r = 0) : n(_n), root(_r), edge(_e), built(false) { edges.reserve(n); }void add_edge(int u, int v, S w = Monoid::e()) {assert(0 <= u && u < n);assert(0 <= v && v < n);assert(!built);edges.emplace_back(u, v, w);}vector<S> rearrange(const vector<S> &a = {}) {build();vector<S> res(n);if (edge) {assert(a.empty());for (auto [u, v, w] : edges) {if (in[u] > in[v]) swap(u, v);res[in[v]] = w;}} else {assert(int(a.size()) == n);for (int u = 0; u < n; u++) {res[in[u]] = a[u];}}return res;}template<typename L>void vertex_set(int u, const S &x, const L &set) {assert(0 <= u && u < n);build();set(in[u], x);}template<typename L>void edge_set(int u, int v, const S &x, const L &set) {assert(edge);assert(0 <= u && u < n);assert(0 <= v && v < n);build();if (in[u] > in[v]) swap(u, v);set(in[v], x);}template<typename L>void edge_set(int i, const S &x, const L &set) {assert(0 <= i && i < n - 1);build();auto &[u, v, w] = edges[i];w = x;edge_set(u, v, x, set);}template<typename F, typename L>void path_apply(int u, int v, const F &f, const L &apply) {assert(0 <= u && u < n);assert(0 <= v && v < n);build();int hu = head[u], hv = head[v];while (hu != hv) {if (in[hu] > in[hv]) {swap(u, v);swap(hu, hv);}apply(in[hu], in[v] + 1, f);v = par[v];hu = head[u];hv = head[v];}if (in[u] > in[v]) swap(u, v);apply(in[u] + edge, in[v] + 1, f);}template<typename F, typename L>void subtree_apply(int u, const F &f, const L &apply) {assert(0 <= u && u < n);build();apply(in[u] + edge, out[u], f);}template<typename L, typename R>S path_prod(int u, int v, const L &prod, const R &rev) {assert(0 <= u && u < n);assert(0 <= v && v < n);bool flip = false;S pu = Monoid::e(), pv = Monoid::e();int hu = head[u], hv = head[v];while (hu != hv) {if (in[hu] > in[hv]) {swap(u, v);swap(hu, hv);swap(pu, pv);flip = !flip;}S p = prod(in[hv], in[v] + 1);pv = Monoid::op(p, pv);v = par[hv];hu = head[u];hv = head[v];}if (in[u] > in[v]) {swap(u, v);swap(pu, pv);flip = !flip;}S p = prod(in[u] + edge, in[v] + 1);pv = Monoid::op(p, pv);pv = Monoid::op(rev(pu), pv);return flip ? rev(pv) : pv;}template<typename L>S path_prod(int u, int v, const L &prod) {return path_prod(u, v, prod, [&](const S &x) { return x; });}template<typename L>S subtree_prod(int u, const L &prod) {assert(0 <= u && u < n);build();return prod(in[u] + edge, out[u]);}private:int n, root, id;vector<vector<int>> g;bool edge, built;vector<int> sub, depth, par, in, out, head, heavy;vector<tuple<int, int, S>> edges;void dfs(int u, int p) {par[u] = p;sub[u] = 1;int sub_max = 0;for (int v : g[u]) {if (v != p) {dfs(v, u);sub[u] += sub[v];if (sub[v] > sub_max) {sub_max = sub[v];heavy[u] = v;}}}}void decompose(int u, int h) {head[u] = h;in[u] = id++;if (heavy[u] != -1) decompose(heavy[u], h);for (int v : g[u]) {if (v != heavy[u] && v != par[u]) {decompose(v, v);}}out[u] = id;}void build() {if (built) return;g.resize(n);sub.resize(n);depth.resize(n);par.resize(n, -1);in.resize(n);out.resize(n);head.resize(n);heavy.resize(n, -1);for (const auto &[u, v, w] : edges) {g[u].push_back(v);g[v].push_back(u);}id = 0;dfs(root, root);decompose(root, root);built = true;}};struct Monoid {using S = int;static S op(S a, S b) { return a ^ b; }static S e() { return 0; }};int main () {ios::sync_with_stdio(false);cin.tie(nullptr);int N, Q;cin >> N >> Q;vector<int> A(N);for (int i = 0; i < N; i++) cin >> A[i];heavy_light_decomposition<Monoid> G(N, false);for (int i = 1; i < N; i++) {int u, v;cin >> u >> v;u--, v--;G.add_edge(u, v);}segtree<Monoid> seg(G.rearrange(A));auto update = [&](int p, int x) -> void {int y = seg.get(p);seg.set(p, x ^ y);};auto prod = [&](int l, int r) -> int {return seg.prod(l, r);};while (Q--) {int t, x, y;cin >> t >> x >> y;if (t == 1) {x--;G.vertex_set(x, y, update);} else {x--;cout << G.subtree_prod(x, prod) << '\n';}}}