树链剖分第一题QAQ，纪念下

#pragma comment(linker, "/STACK:102400000,102400000")

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

typedef long long ll;

const ll mod = 1e9 + 7;

const int maxn = 1e5 + 10;

#define to first

#define next second

#define foreach(it,v) for(__typeof(v.begin()) it = v.begin(); it != v.end(); ++it)

int pos[maxn],head[maxn],fa[maxn],son[maxn];

int a[maxn],siz[maxn],root[maxn],dep[maxn];

typedef pair<int,int> Edge;

Edge edges[maxn<<1];

int e,tot;

void AddEdge(int u,int v)

{

    edges[++e] = make_pair(v,head[u]);head[u] = e;

    edges[++e] = make_pair(u,head[v]);head[v] = e;

}

void pre(int u)

{

    siz[u] = 1;son[u] = 0;

    dep[u] = dep[fa[u]] + 1;

    for(int i = head[u]; i ; i = edges[i].next) {

        int v = edges[i].to;

        if(v == fa[u])continue;

        fa[v] = u;

        pre(v);

        siz[u] += siz[v];

        if(siz[son[u]] < siz[v]) son[u] = v;

    }

}

void built(int u,int t)

{

    root[u] = t;

    pos[u] = ++tot;

    if(son[u] < 1) return;

    built(son[u],t);

    for(int i = head[u]; i ; i = edges[i].next) {

        int v = edges[i].to;

        if(v == fa[u] || v == son[u])continue;

        built(v,v);

    }

}

int seg[maxn<<2];

int ql,qr,x,v;

void Modify(int o,int L,int R)

{

    if(L == R) {

        seg[o] = v;

        return ;

    }

    int mid = (L+R)>>1;

    if(x<=mid) Modify(o<<1,L,mid);

    else Modify(o<<1|1,mid+1,R);

    seg[o] = seg[o<<1] ^ seg[o<<1|1];

}

int Queryseg(int o,int L,int R)

{

    if(ql<=L&&qr>=R) return seg[o];

    int mid = (L+R) >> 1;

    int res = 0;

    if(ql <= mid) res = Queryseg(o<<1,L,mid);

    if(qr > mid) res ^= Queryseg(o<<1|1,mid+1,R);

    return res;

}

int solve(int u,int v)

{

    int res = 0;

    while(root[u] != root[v]) {

        if(dep[root[u]] < dep[root[v]]) swap(u,v);

        ql = pos[root[u]],qr = pos[u];

        res ^= Queryseg(1,1,tot);

        u = fa[root[u]];

    }

    ql = pos[u],qr = pos[v];

    if(ql > qr) swap(ql,qr);

    res ^= Queryseg(1,1,tot);

    return res;

}

int main(int argc, char const *argv[])

{

    int T;scanf("%d",&T);

    while(T--) {

        int N,Q;scanf("%d%d",&N,&Q);

        dep[0] = e = tot = 0;

        memset(seg,0,sizeof seg);

        memset(head,0,sizeof(head[0])*(N+1));

        for(int i = 1; i < N; i++) {

            int u,v;scanf("%d%d",&u,&v);

            AddEdge(u,v);

        }

        fa[1] = siz[0] = 0;

        pre(1);

        built(1,1);

        for(int i = 1; i <= N; i++) {

            scanf("%d",&v); ++v; x = pos[i];

            Modify(1,1,tot);

        }

        while(Q--) {

            int op;scanf("%d",&op);

            if(op==0) {

                scanf("%d%d",&x,&v);x = pos[x]; ++v;

                Modify(1,1,tot);

            } else {

                scanf("%d%d",&ql,&qr);

                int ans = solve(ql,qr);

                printf("%d\n", ans - 1);

            }

        }

    }

    return 0;

}