[题目链接]

https://www.lydsy.com/JudgeOnline/problem.php?id=5338

[算法]

首先对这棵树进行树链剖分

那么我们就将一个树上的问题转化为一个序列上的问题

建立可持久化字典树维护最大异或值即可

时间复杂度 : O(NlogN ^ 2)

[代码]

#include
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int N = 2e5 + ;
const int MAXLOG = ;

struct edge
{
int to , nxt;
} e[N << ];

int n , tot , timer , q;
int head[N] , size[N] , top[N] , a[N] , perm[N] , l[N] , r[N] , son[N] , father[N] , depth[N] , rt[N];

struct Presitent_Trie
{
int sz;
int child[N * MAXLOG][] , latest[N * MAXLOG];
Presitent_Trie()
{
sz = ;
}
inline void modify(int bit , int &now , int old , int x , int loc)
{
now = ++sz;
child[now][] = child[old][] , child[now][] = child[old][];
latest[now] = loc;
if (bit < ) return; int value = ; if (x & ( << bit)) value = ; modify(bit - , child[now][value] , child[old][value] , x , loc); } inline int query(int bit , int now , int lft , int x) { if (bit < ) return ; int value = ; if (x & ( << bit)) value = ; if (latest[child[now][value]] >= lft) return ( << bit) + query(bit - , child[now][value] , lft , x);
else return query(bit - , child[now][value ^ ] , lft , x);
}
} PT;

template inline void chkmax(T &x,T y) { x = max(x,y); }
template inline void chkmin(T &x,T y) { x = min(x,y); }
template inline void read(T &x)
{
T f = ; x = ;
char c = getchar();
for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
for (; isdigit(c); c = getchar()) x = (x << ) + (x << ) + c - ''; x *= f; } inline void addedge(int u , int v) { ++tot; e[tot] = (edge){v , head[u]}; head[u] = tot; } inline void dfs1(int u , int par) { size[u] = ; depth[u] = depth[par] + ; father[u] = par; for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; if (v == par) continue; dfs1(v , u); size[u] += size[v]; if (size[v] > size[son[u]]) son[u] = v;
}
}
inline void dfs2(int u , int t)
{
top[u] = t;
l[u] = ++timer;
if (son[u]) dfs2(son[u] , t);
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].to;
if (v == father[u] || v == son[u]) continue;
dfs2(v , v);
}
r[u] = timer;
}
inline bool cmp(int x , int y)
{
return l[x] < l[y]; } inline int query(int x , int y , int z) { int ans = ; while (top[x] != top[y]) { if (depth[top[x]] > depth[top[y]]) swap(x , y);
chkmax(ans , PT.query(MAXLOG - , rt[l[y]] , l[top[y]] , z));
y = father[top[y]];
}
if (depth[x] > depth[y]) swap(x , y);
chkmax(ans , PT.query(MAXLOG - , rt[l[y]] , l[x] , z));
return ans;
}

int main()
{

    read(n); read(q);  
    for (int i = ; i <= n; ++i) read(a\[i\]);  
    for (int i = ; i < n; ++i)  
    {  
            int x , y;  
            read(x); read(y);  
            addedge(x , y);  
            addedge(y , x);  
    }  
    dfs1( , );  
    dfs2( , );  
    for (int i = ; i <= n; ++i) perm\[i\] = i;  
    sort(perm +  , perm + n +  , cmp);  
    for (int i = ; i <= n; ++i) PT.modify(MAXLOG -  , rt\[i\] , rt\[i - \] , a\[perm\[i\]\] , i);  
    while (q--)  
    {  
            int type;  
            read(type);  
            if (type == )  
            {  
                    int x , y;  
                    read(x); read(y);  
                    printf("%d\\n" , PT.query(MAXLOG -  , rt\[r\[x\]\] , l\[x\] , y));  
            }    else  
            {  
                    int x , y , z;  
                    read(x); read(y); read(z);  
                    printf("%d\\n" , query(x , y , z));  
            }  
    }

    return ;

}