結果

問題 No.1641 Tree Xor Query
コンテスト
ユーザー bolero
提出日時 2025-05-20 22:42:29
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 330 ms / 5,000 ms
コード長 4,526 bytes
コンパイル時間 5,461 ms
コンパイル使用メモリ 334,072 KB
実行使用メモリ 30,848 KB
最終ジャッジ日時 2025-05-20 22:42:38
合計ジャッジ時間 8,197 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
#define FOR(i, s, e) for (long long i = (long long)(s); i <= (long long)(e); i++)
#define printYesNo(is_ok) puts(is_ok ? "Yes" : "No");
#define SORT(v) sort(v.begin(), v.end());
#define RSORT(v) sort(v.rbegin(), v.rend());
#define REVERSE(v) reverse(v.begin(), v.end());

class HeavyLightDecomposition
{
public:
    HeavyLightDecomposition(int n)
        : n(n), edges(n), parent(n, -1), depth(n, 0), heavy(n, -1), head(n), in_time(n), sz(n), built(false)
    {
    }

    void add_edge(int u, int v)
    {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        edges[u].push_back(v);
        edges[v].push_back(u);
    }

    void build(int root = 0)
    {
        assert(0 <= root && root < n);
        if (built)
        {
            return;
        }

        parent[root] = -1;
        depth[root] = 0;
        dfs_size(root);
        int time = 0;
        decompose(root, root, time);
        built = true;
    }

    vector<array<int, 2>> get_path_ranges(int u, int v)
    {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        ensure_built();

        vector<array<int, 2>> ranges;

        while (head[u] != head[v])
        {
            if (depth[head[v]] < depth[head[u]])
            {
                ranges.push_back({in_time[head[u]], in_time[u] + 1});
                u = parent[head[u]];
            }
            else
            {
                ranges.push_back({in_time[head[v]], in_time[v] + 1});
                v = parent[head[v]];
            }
        }

        if (depth[v] < depth[u])
        {
            swap(u, v);
        }

        ranges.push_back({in_time[u], in_time[v] + 1});
        return ranges;
    }

    array<int, 2> get_subtree_range(int u)
    {
        assert(0 <= u && u < n);

        ensure_built();
        return {in_time[u], in_time[u] + sz[u]};
    }

    int lca(int u, int v)
    {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);

        ensure_built();
        while (head[u] != head[v])
        {
            if (depth[head[u]] > depth[head[v]])
            {
                swap(u, v);
            }
            v = parent[head[v]];
        }
        return depth[u] < depth[v] ? u : v;
    }

    int get_in_time(int v)
    {
        assert(0 <= v && v < n);

        ensure_built();
        return in_time[v];
    }

    int get_subtree_size(int u)
    {
        assert(0 <= u && u < n);

        ensure_built();
        return sz[u];
    }

private:
    int n;
    vector<vector<int>> edges;
    vector<int> parent, depth, heavy, head, in_time, sz;
    bool built;

    void ensure_built()
    {
        if (!built)
        {
            build();
        }
    }

    int dfs_size(int v)
    {
        sz[v] = 1;
        int max_size = 0;
        for (int u : edges[v])
        {
            if (u == parent[v])
            {
                continue;
            }
            parent[u] = v;
            depth[u] = depth[v] + 1;
            int sub = dfs_size(u);
            sz[v] += sub;
            if (sub > max_size)
            {
                max_size = sub;
                heavy[v] = u;
            }
        }
        return sz[v];
    }

    void decompose(int v, int h, int &time)
    {
        head[v] = h;
        in_time[v] = time++;
        if (heavy[v] != -1)
        {
            decompose(heavy[v], h, time);
        }

        for (int u : edges[v])
        {
            if (u == parent[v] || u == heavy[v])
            {
                continue;
            }

            decompose(u, u, time);
        }
    }
};

using S = int;
S op(S a, S b) { return a ^ b; }
S e() { return 0; }

int main()
{
    int N, Q;
    cin >> N >> Q;

    vector<int> C(N);
    rep(i, N)
    {
        cin >> C[i];
    }

    HeavyLightDecomposition hld(N);
    rep(i, N - 1)
    {
        int a, b;
        cin >> a >> b;
        hld.add_edge(a - 1, b - 1);
    }

    hld.build();

    atcoder::segtree<S, op, e> seg(N);
    rep(i, N)
    {
        seg.set(hld.get_in_time(i), C[i]);
    }

    rep(_, Q)
    {
        int T, x, y;
        cin >> T >> x >> y;
        x--;
        if (T == 1)
        {
            int xi = hld.get_in_time(x);
            seg.set(xi, seg.get(xi) ^ y);
        }

        if (T == 2)
        {
            auto [l, r] = hld.get_subtree_range(x);
            cout << seg.prod(l, r) << endl;
        }
    }

    return 0;
};
0