Dylans is given a tree with N nodes.

All nodes have a value A[i].Nodes on tree is numbered by 1∼N.

Then he is given Q questions like that:

①0 x y：change node x′s value to y

②1 x y：For all the value in the path from x to y,do they all appear even times?

For each ② question,it guarantees that there is at most one value that appears odd times on the path.

1≤N,Q≤100000, the value A[i]∈N and A[i]≤100000

 

In the first line there is a test number T.
(T≤3 and there is at most one testcase that N>1000)

For each testcase:

In the first line there are two numbers N and Q.

Then in the next N−1 lines there are pairs of (X,Y) that stand for a road from x to y.

Then in the next line there are N numbers A1..AN stand for value.

In the next Q lines there are three numbers(opt,x,y).

 

For each question ② in each testcase,if the value all appear even times output "-1",otherwise output the value that appears odd times.

 

 

 

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

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

#define ls i<<1

#define rs ls | 1

#define mid ((ll+rr)>>1)

#define pii pair<int,int>

#define MP make_pair

typedef long long LL;

const long long INF = 1e18+1LL;

const double Pi = acos(-1.0);

const int N = 1e6+, M = 1e3+, mod = 1e9+, inf = 2e9;

int dep[N],head[N],t=,sz[N],fa[N],indexS,top[N],pos[N];

struct ss{int to,next;}e[N*];

int n;

void add(int u,int v)

{e[t].to = v;e[t].next = head[u];head[u] = t++;}

void dfs(int u) {

    sz[u] = ;

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

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

        int to = e[i].to;

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

        fa[to] = u;

        dfs(to);

        sz[u] += sz[to];

    }

}

void dfs(int u,int chain) {

    int k = ;

    pos[u] = ++indexS;

    top[u] = chain;

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

        int to = e[i].to;

        if(dep[to] > dep[u] && sz[to] > sz[k])

            k = to;

    }

    if(k == ) return ;

    dfs(k,chain);

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

        int to = e[i].to;

        if(dep[to] > dep[u] && k != to)

            dfs(to,to);

    }

}

int sum[N],fposs[N];

void push_up(int i,int ll,int rr) {

    sum[i] = sum[ls] ^ sum[rs];

}

void build(int i,int ll,int rr) {

    if(ll == rr) {

        sum[i] = fposs[ll];

        return ;

    }

    build(ls,ll,mid),build(rs,mid+,rr);

    push_up(i,ll,rr);

}

void update(int i,int ll,int rr,int x,int c) {

    if(ll == rr) {

        sum[i] = c;

        return ;

    }

    if(x <= mid) update(ls,ll,mid,x,c);

    else update(rs,mid+,rr,x,c);

    push_up(i,ll,rr);

}

int query(int i,int ll,int rr,int x,int y) {

    if(ll == x && rr == y) {

        return sum[i];

    }

    if(y <= mid) return query(ls,ll,mid,x,y);

    else if(x > mid) return query(rs,mid+,rr,x,y);

    else return query(ls,ll,mid,x,mid)^query(rs,mid+,rr,mid+,y);

}

int query(int x,int y) {

    int res = ;

    while(top[x] != top[y]) {

        if(dep[top[x]] > dep[top[y]]) {

            res ^= query(,,indexS,pos[top[x]],pos[x]);

            x = fa[top[x]];

        }

        else {

            res ^= query(,,indexS,pos[top[y]],pos[y]);

            y = fa[top[y]];

        }

    }

    if(dep[x] < dep[y])res ^= query(,,n,pos[x],pos[y]);

    else res ^= query(,,n,pos[y],pos[x]);

    return res;

}

int T,Q,a[N];

void init() {

    t = ;

    memset(fa,,sizeof(fa));

    memset(head,,sizeof(head));

    memset(dep,,sizeof(dep));

    memset(sz,,sizeof(sz));

    memset(top,,sizeof(top));

    memset(pos,,sizeof(pos));

    indexS = ;

}

int main() {

    scanf("%d",&T);

    while(T--) {

        scanf("%d%d",&n,&Q);

        init();

        for(int i = ; i < n; ++i) {

            int x,y;

            scanf("%d%d",&x,&y);

            add(x,y);add(y,x);

        }

        dfs();

        dfs(,);

        for(int i = ; i <= n; ++i) scanf("%d",&a[i]);

        for(int i = ; i <= n; ++i) fposs[pos[i]] = a[i]+;

        build(,,indexS);

        while(Q--) {

            int op,x,y;

            scanf("%d%d%d",&op,&x,&y);

            if(op == ) {

                update(,,indexS,pos[x],y+);

            } else {

                printf("%d\n",query(x,y)-);

            }

        }

    }

    return ;

}