题面
Sol
显然是要维护一个区域的 (trie) 树，然后贪心
区间 (trie) 树？？？
可持久化 (trie) 树？？？
直接参考主席树表示出区间的方法建立 (trie) 树，然后做差就好了
巨简单
# include <bits/stdc++.h>
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
IL int Input(){
RG int x = 0, z = 1; RG char c = getchar();
for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
return x * z;
}
const int maxn(1e5 + 5);
const int pw(1 << 30);
int n, q, first[maxn], cnt, val[maxn], dfn[maxn], idx, id[maxn];
int size[maxn], son[maxn], top[maxn], deep[maxn], fa[maxn];
struct Edge{
int to, next;
} edge[maxn << 1];
struct Trie{
int ch[2][maxn * 32], rt[maxn], tot, sz[maxn * 32];
IL void Modify(RG int &x, RG int v, RG int d){
ch[0][++tot] = ch[0][x], ch[1][tot] = ch[1][x];
sz[tot] = sz[x] + 1, x = tot;
if(!d) return;
Modify(ch[bool(d & v)][x], v, d >> 1);
}
IL int Query1(RG int a, RG int b, RG int v, RG int dep){
if(!a || !dep) return 0;
RG int f = bool(dep & v) ^ 1, s = sz[ch[f][a]] - sz[ch[f][b]];
if(s) return Query1(ch[f][a], ch[f][b], v, dep >> 1) + dep;
f ^= 1;
return Query1(ch[f][a], ch[f][b], v, dep >> 1);
}
IL int Query2(RG int a, RG int b, RG int c, RG int d, RG int v, RG int dep){
if(!(a + b) || !dep) return 0;
RG int f = bool(dep & v) ^ 1, s = sz[ch[f][a]] + sz[ch[f][b]] - sz[ch[f][c]] - sz[ch[f][d]];
if(s) return Query2(ch[f][a], ch[f][b], ch[f][c], ch[f][d], v, dep >> 1) + dep;
f ^= 1;
return Query2(ch[f][a], ch[f][b], ch[f][c], ch[f][d], v, dep >> 1);
}
} tree1, tree2;
IL void Add(RG int u, RG int v){
edge[cnt] = (Edge){v, first[u]}, first[u] = cnt++;
}
IL void Dfs1(RG int u, RG int ff){
size[u] = 1, tree1.rt[u] = tree1.rt[ff];
tree1.Modify(tree1.rt[u], val[u], pw);
for(RG int e = first[u]; e != -1; e = edge[e].next){
RG int v = edge[e].to;
if(v != ff){
deep[v] = deep[u] + 1, fa[v] = u;
Dfs1(v, u);
size[u] += size[v];
if(size[v] > size[son[u]]) son[u] = v;
}
}
}
IL void Dfs2(RG int u, RG int tp){
dfn[u] = ++idx, id[idx] = u, top[u] = tp;
if(son[u]) Dfs2(son[u], tp);
for(RG int e = first[u]; e != -1; e = edge[e].next)
if(!dfn[edge[e].to]) Dfs2(edge[e].to, edge[e].to);
}
IL int LCA(RG int u, RG int v){
while(top[u] ^ top[v])
deep[top[u]] > deep[top[v]] ? u = fa[top[u]] : v = fa[top[v]];
return deep[u] > deep[v] ? v : u;
}
int main(){
n = Input(), q = Input();
for(RG int i = 1; i <= n; ++i) val[i] = Input(), first[i] = -1;
for(RG int i = 1; i < n; ++i){
RG int u = Input(), v = Input();
Add(u, v), Add(v, u);
}
Dfs1(1, 0), Dfs2(1, 0);
for(RG int i = 1; i <= n; ++i){
tree2.rt[i] = tree2.rt[i - 1];
tree2.Modify(tree2.rt[i], val[id[i]], pw);
}
for(RG int i = 1; i <= q; ++i)
if(Input() == 1){
RG int u = Input(), v = Input();
printf("%d
", tree2.Query1(tree2.rt[dfn[u] + size[u] - 1], tree2.rt[dfn[u] - 1], v, pw));
}
else{
RG int u = Input(), v = Input(), x = Input(), lca = LCA(u, v);
printf("%d
", tree1.Query2(tree1.rt[u], tree1.rt[v], tree1.rt[lca], tree1.rt[fa[lca]], x, pw));
}
return 0;
}