HDU-5274 Dylans loves tree(树剖模板题)

题目链接 - HDU 5274

题目简述：

一棵树有n个节点，每次修改其中一个节点的权值，或者查询从u到v的路径上所有的节点里面是否有出现奇数个的权值
例如：一个路径上出现了 2 2 4 5 5，那答案就是4，题目保证每次查询路径上只有一个点出现奇数次。

题目思路：

这就是一个树上的节点修改，非常简单的树剖模板题。因为题目保证只有一个点出现奇数次，所以用树状数组维护异或和即可。当一个数字出现偶数次，异或和就会重新变为0。但这题有个坑点，a[i]∈N，N为自然数，所以有可能权值为0。所以在树状数组里维护权值+1的异或和即可，每次输出答案-1，这样当没有答案的时候正好可以输出-1。

代码：

// 巨菜的ACMer-Happier233

#include <bits/stdc++.h>

using namespace std;

//-----
typedef double db;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define fi first
#define se second
#define pw(x) (1ll << (x))
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rep(i, l, r) for(int i=(l);i<(r);++i)
#define per(i, l, r) for(int i=(r)-1;i>=(l);--i)
#define sf(x) scanf("%d", &(x))

#define foreg(i, s, eg) for(int i = (s); ~i; i = (eg)[i].nxt)

const double pi = acos(-1);
const ll MOD = ll(1e9 + 7);

struct Edge {
    int e, nxt;
    ll v;

    Edge() = default;

    Edge(int a, ll b, int c = 0) : e(a), v(b), nxt(c) {}

    bool operator<(const Edge &a) const {
        return (a.v == v ? e < a.e : v < a.v);
    }
};

const ll INF = ll(1e11);
const int N = int(2e5 + 10);
const int M = int(6e5 + 10);

struct Graph {
    Edge eg[M];
    int head[N];
    int cnt;

    void init(int n) {
        memset(head, -1, sizeof(int) * ++n);
        cnt = 0;
    }

    inline void addEdge(int x, int y, ll v) {
        eg[cnt] = Edge(y, v, head[x]);
        head[x] = cnt++;
    }

    inline int begin(int p) {
        return head[p];
    }

    inline Edge &operator[](int i) {
        return eg[i];
    }

    inline int next(int i) {
        return eg[i].nxt;
    }
} gh;

struct TreeChain {
    int top[N]; // 链条顶端点ID
    int fa[N]; // 父亲节点
    int son[N]; // 重儿子
    int deep[N]; // 深度
    int num[N]; // 儿子节点数（包括自己）


    int p[N]; // 点在线段树中的ID
    int fp[N]; // 线段树中ID对应的点
    int fe[N]; // 每个点到父亲节点的边ID
    int ep[N]; // 每个点到父节点对应的边在线段树中的ID
    // int fep[N]; // 线段树中ID对应的边
    int tot;

    void dfs(int u, int pre, int d) {
        num[u] = 1;
        deep[u] = d;
        fa[u] = pre;
        son[u] = -1;
        fe[u] = -1;
        for (int i = gh.head[u]; ~i; i = gh.eg[i].nxt) {
            int v = gh.eg[i].e;
            if (v == pre) {
                fe[u] = i;
                continue;
            }
            dfs(v, u, d + 1);
            num[u] += num[v];
            if (son[u] == -1 || num[v] > num[son[u]]) {
                son[u] = v;
            }
        }
    }

    void getpos(int u, int sp) {
        top[u] = sp;
        p[u] = tot++;
        fp[p[u]] = u;
        ep[fe[u] >> 1] = p[u];
        if (son[u] == -1) return;
        getpos(son[u], sp);
        for (int i = gh.head[u]; ~i; i = gh.eg[i].nxt) {
            int v = gh.eg[i].e;
            if (v == son[u] || v == fa[u]) continue;
            getpos(v, v);
        }
    }

    void build(int start, int root) {
        tot = start; // start是线段树中的ID起始数值
        dfs(root, 0, 0);
        getpos(root, root);
    }
} treec;

struct BITree {
    int n;
    ll c[N];

    void init(int _n) {
        n = _n;
        memset(c, 0, sizeof(ll) * ++n);
    }

    void change(int pos, ll v) {
        for (int i = pos; i < n; i += i & (-i))
            c[i] ^= v;
    }

    ll query(int x) {
        ll ans = 0;
        for (int i = x; i > 0; i -= i & (-i))
            ans ^= c[i];
        return ans;
    }

    ll query(int l, int r) {
        if (r < l) swap(l, r);
        return query(r) ^ query(l - 1);
    }
} tree;

ll query(int u, int v) {
    int f1 = treec.top[u];
    int f2 = treec.top[v];
    ll ans = 0;
    while (f1 != f2) {
        if (treec.deep[f1] < treec.deep[f2]) {
            swap(f1, f2);
            swap(u, v);
        }
        ans ^= tree.query(treec.p[f1], treec.p[u]);
        u = treec.fa[f1];
        f1 = treec.top[u];
    }
    if (treec.deep[u] > treec.deep[v]) {
        swap(u, v);
    }
    ans ^= tree.query(treec.p[u], treec.p[v]);
    return ans;
}

int _tc = 0;
int val[N];

void solve() {
    int n, m, q;
    cin >> n >> q;
    m = n - 1;
    gh.init(n);
    tree.init(n);
    rep(i, 0, m) {
        int a, b;
        cin >> a >> b;
        gh.addEdge(a, b, 0);
        gh.addEdge(b, a, 0);
    }
    rep(i, 0, n) {
        cin >> val[i + 1];
        val[i + 1]++;
    }
    treec.build(1, 1);
    rep(i, 0, n) {
        int p = treec.p[i + 1];
        tree.change(p, val[i + 1]);
    }
    rep(i, 0, q) {
        int c, x, y;
        cin >> c >> x >> y;
        if (c == 1) {
            ll ans = query(x, y);
            cout << (ans - 1) << endl;
        } else {
            tree.change(x, val[x]);
            tree.change(x, val[x] = y + 1);
        }
    }
}


int main() {
#ifdef ACM_LOCAL
    freopen("./data/std.in", "r", stdin);
    // freopen("./data/std.out", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#endif
    int t;
    cin >> t;
    while (t--)
        solve();
    return 0;
}