bestcoder round#45 1003 题，给定两个点，要我们求这两个点的树上路径所经过的点的权值是否出现过奇数次。
如果是一般人，那么就是用lca求树上路径，然后判断是否出现过奇数次（用异或），高手就不这么做了，直接树链剖分。
为什么不能用lca，因为如果有树退化成链，那么每次询问的复杂度是O(n)， 那么q次询问的时间复杂度是O(qn)
什么是树链剖分呢？ 就是把树的边分成轻链和重链
http://blog.sina.com.cn/s/blog_6974c8b20100zc61.html
http://www.cnblogs.com/BLADEVIL/p/3479713.html
这两个博客写的很好了
剖分后的树有如下性质：
1、如果（u，v)为轻边， 那么 size[v]*2<size[u]
2、从根到某一点的路径上的轻链，重链的个数不大于logn
所以我们可以用线段树来维护这些链，这样如果 要得到任意两点树上路径的信息，那么只要访问线段树，那么时间复杂度只要4logn*logn
第一次dfs进行树链剖分，求出了轻链和重链
第二次dfs对树的结点进行了重新编号（结点的编号就是在线段树中区间中的一点）， 重链上的结点的编号是连续的
那么重链上的点在线段树中的区间是连续的。
那么要询问树上任意两点路径权值的最大值， 只要上depth大的那个点往上走， 如果往上走的时候，遇到的重链，那么可以进去区间查询，然后一次
走过重链即可。
对于bestcoder round#45 1003 题，
第二次dfs求出编号后，建线段树，然后区间的值等于子区间的异或
那么任意两点的树上路径的权值是否重复，只要访问线段树区间，看最后的异或的值是为0
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <math.h>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#pragma warning(disable:4996)
typedef long long LL;
const int INF = <<;
void input(int &x)
{
char ch = getchar();
while (ch<'' || ch>'')
ch = getchar();
x = ;
while (ch >= ''&&ch <= '')
{
x = x * + ch - '';
ch = getchar();
}
}
/*
第一次dfs进行树链剖分，求出了轻链和重链
第二次dfs对树的结点进行了重新编号， 重链上的结点的编号是连续的
那么重链上的点在线段树中的区间是连续的
剖分后的树有如下性质：
性质1：如果(v,u)为轻边，则siz[u] * 2 < siz[v]；
性质2：从根到某一点的路径上轻链、重链的个数都不大于logn。 那么要询问树上任意两点路径权值的最大值， 只要上depth大的那个点往上走， 如果往上走的时候，遇到的重链，那么可以进去区间查询，然后一次
走过重链
根据性质2：每次询问的复杂度是O(logn*logn)
*/
const int N = + ;
int size[N], depth[N], son[N], fa[N], w[N], top[N], ra[N], num;
int value[N];
int tree[N * ];
vector<int> g[N];
int ans;
void dfs(int u)
{
size[u] = ;
son[u] = ;
for (int i = ; i < g[u].size(); ++i)
{
int v = g[u][i];
if (v != fa[u])
{
depth[v] = depth[u] + ;
fa[v] = u;
dfs(v);
size[u] += size[v];
if (size[v]>size[son[u]])
son[u] = v;
}
}
}
void dfs2(int u, int tp)
{
top[u] = tp;
w[u] = ++num;//对树上的结点进行编号
ra[num] = u;
//因为优先dfs重儿子，所以一条重链上的点的编号是连续的
if (son[u] != )
dfs2(son[u], top[u]);
for (int i = ; i < g[u].size(); ++i)
{
int v = g[u][i];
if (v != son[u] && v != fa[u])
dfs2(v, v);
}
}
void pushUp(int rt)
{
tree[rt] = tree[rt << ] ^ tree[rt << | ];
}
void build(int l, int r, int rt)
{
if (l == r)
{
tree[rt] = value[ra[l]];//ra[l] 是编号为l的是哪个结点
return;
}
int mid = (l + r) >> ;
build(l, mid, rt << );
build(mid + , r, rt << | );
pushUp(rt);
}
//修改某个结点的值， 那么要将父区间异或旧的值（即去除原先的值），然后异或新的值
void update(int l, int r, int rt, int pos, int newVal, int oldVal)
{
tree[rt] = tree[rt] ^ oldVal^newVal;
if (l == r)
return;
int mid = (l + r) >> ;
if (pos <= mid)
update(l, mid, rt << , pos, newVal, oldVal);
else
update(mid + , r, rt << | , pos, newVal, oldVal);
}
void query(int l, int r, int rt, int L, int R)
{
if (L <= l && R >= r)
{
ans ^= tree[rt];
return;
}
int mid = (l + r) >> ;
if (L <= mid)
query(l, mid, rt << , L, R);
if (R > mid)
query(mid + , r, rt << | , L, R);
}
int main()
{
int t, n, q, op,a, b;
scanf("%d", &t);
while (t--)
{
num = ;
scanf("%d%d", &n, &q);
for (int i = ; i <= n; ++i)
g[i].clear();
for (int i = ; i < n; ++i)
{
scanf("%d%d", &a, &b);
g[a].push_back(b);
g[b].push_back(a);
}
for (int i = ; i <= n; ++i)
{
//scanf("%d", &value[i]);
input(value[i]);
value[i]++;
}
depth[] = fa[] = ;
dfs();
dfs2(, );
build(, n, );
while (q--)
{
scanf("%d%d%d", &op, &a, &b); if (op == )
{
b++;
update(, n, , w[a], b, value[a]);
value[a] = b;
}
else
{
ans = ;
//不停的往上走，像lca一样，不过比lca更优，因为有重链的存在，可以一次走很多部
while (top[a] != top[b])
{
if (depth[top[a]] < depth[top[b]])
swap(a, b);
query(, n, , w[top[a]], w[a]);
a = fa[top[a]];
}
if (depth[a] > depth[b])
swap(a, b);
query(, n, , w[a], w[b]);
if (ans == )
printf("%d\n", -);
else
printf("%d\n", ans - );
}
}
}
return ;
}