[SCOI2016]幸运数字

Description

A 国共有 \(n\) 座城市，这些城市由 \(n - 1\) 条道路相连，使得任意两座城市可以互达，且路径唯一。每座城市都有一个幸运数字，以纪念碑的形式矗立在这座城市的正中心，作为城市的象征。一些旅行者希望游览 A 国。旅行者计划乘飞机降落在 \(x\) 号城市，沿着 \(x\) 号城市到 \(y\) 号城市之间那条唯一的路径游览，最终从 \(y\) 城市起飞离开 A 国。

在经过每一座城市时，游览者就会有机会与这座城市的幸运数字拍照，从而将这份幸运保存到自己身上。然而，幸运是不能简单叠加的，这一点游览者也十分清楚。他们迷信着幸运数字是以异或的方式保留在自己身上的。例如，游览者拍了 3 张照片，幸运值分别是 5、7、11，那么最终保留在自己身上的幸运值就是 9（\(5 \mathbin{\text{xor}} 7 \mathbin{\text{xor}} 11\)）。

有些聪明的游览者发现，只要选择性地进行拍照，便能获得更大的幸运值。例如在上述三个幸运值中，只选择 5 和 11 ，可以保留的幸运值为 14 。现在，一些游览者找到了聪明的你，希望你帮他们计算出在他们的行程安排中可以保留的最大幸运值是多少。

Input

第一行包含两个正整数 \(n\)、\(q\)，分别表示城市的数量和旅行者数量。
第二行包含 \(n\) 个非负整数，其中第 \(i\) 个整数 \(G_i\) 表示 \(i\) 号城市的幸运值。随后 \(n - 1\) 行，每行包含两个正整数 \(x\)、\(y\)，表示 \(x\) 号城市和 \(y\) 号城市之间有一条道路相连。
随后 \(q\) 行，每行包含两个正整数 \(x\)、\(y\)，表示这名旅行者的旅行计划是从 \(x\) 号城市到 \(y\) 号城市。

Output

输出需要包含 \(q\) 行，每行包含 1 个非负整数，表示这名旅行者可以保留的最大幸运值。

Sample Input

4 2
11 5 7 9
1 2
1 3
1 4
2 3
1 4

Sample Output

14
11

HINT

\(N\leqslant 2\times 10^4,Q\leqslant 2\times 10^5,G_i\leqslant 2^{60}\)

\(\mathrm{Xor}\)最大值？很明显线性基

树上路径？树剖！

于是我们可以考虑将线段树的节点换成线性基，非叶子节点就是左右俩儿子线性基的合并。

怎么合并？\(O(K)\)枚举插入（\(K=60\)），时间复杂度为\(O(K^2)\)

树剖时间复杂度是常数很小的\(O(n\log^2n)\)

所以总时间复杂度？\(O(K^2n\log^2 n)\)，大概在8e7的级别。常数很小随便过

注意一下，线段树\(\mathrm{Query}\)操作的时候，不要将整个\(\mathrm{Query}\)作为一个线性基去合并，我们只关心终止节点的值，因此我们传入形参的引用，在终止节点合并当前节点的线性基即可。

/*program from Wolfycz*/
#include
#include
#include
#include
#include
#include
#include
#include
#define Fi first
#define Se second
#define lMax 1e18
#define MK make_pair
#define iMax 0x7f7f7f7f
#define sqr(x) ((x)*(x))
#define pii pair
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
templateinline T read(T x){
    int f=1; char ch=getchar();
    for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')	f=-1;
    for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<1)+(x<<3)+ch-'0';
    return x*f;
}
inline void print(int x){
    if (x<0)	putchar('-'),x=-x;
    if (x>9)	print(x/10);
    putchar(x%10+'0');
}
const int N=2e4,M=60;
class Xor_Line{
private:
    ll A[M+10];
public:
    Xor_Line(){memset(A,0,sizeof(A));}
    void insert(ll x);
    void merge(Xor_Line &_XL);
    ll operator [](const int index){return A[index];}
    ll Max();
}XL;
void Xor_Line::insert(ll x){
    for (int i=M;~i;i--){
        if (x&(1ll<Ans)
            Ans^=A[i];
    return Ans;
}

ll V[N+10]; int _Dfn[N+10];
class SegMent_Tree{
#define ls (p<<1)
#define rs (p<<1|1)
private:
    Xor_Line Q[(N<<2)+10];
    void update(int p);
public:
    SegMent_Tree()=default;
    SegMent_Tree(const SegMent_Tree &_ST)=delete;
    SegMent_Tree& operator=(const SegMent_Tree &_ST)=delete;
    void build(int p,int l,int r);
    void Query(int p,int l,int r,int L,int R,Xor_Line& Ans);
}ST;
void SegMent_Tree::update(int p){
    Q[p].merge(Q[ls]);
    Q[p].merge(Q[rs]);
}
void SegMent_Tree::build(int p, int l, int r){
    if (l==r){
        Q[p].insert(V[_Dfn[l]]);
        return;
    }
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
    update(p);
}
void SegMent_Tree::Query(int p, int l, int r, int L, int R, Xor_Line &Ans){
    if (L<=l&&r<=R){
        Ans.merge(Q[p]);
        return;
    }
    int mid=(l+r)>>1;
    if (L<=mid) Query(ls,l,mid,L,R,Ans);
    if (R>mid)  Query(rs,mid+1,r,L,R,Ans);
}
#undef ls
#undef rs

int Time;
class HLD{//Heavy_Light_Decomposition
private:
    int pre[(N<<1)+10],now[N+10],child[(N<<1)+10],tot;
    int Heavy[N+10],Size[N+10],Dfn[N+10],Top[N+10],Fa[N+10],Deep[N+10];
    void join(int x,int y);
public:
    HLD()=default;
    HLD(const HLD &_HLD)=delete;
    HLD& operator=(const HLD &_HLD)=delete;
    void insert(int x,int y);
    void Dfs1(int x,int fa);
    void Dfs2(int x,int fa);
    void solve(int x,int y,int n);
}HLD;
void HLD::join(int x, int y){
    pre[++tot]=now[x],now[x]=tot,child[tot]=y;
}
void HLD::insert(int x, int y){
    join(x,y),join(y,x);
}
void HLD::Dfs1(int x, int fa){
    Size[x]=1,Deep[x]=Deep[Fa[x]=fa]+1;
    for (int p=now[x];p;p=pre[p]){
        int son=child[p];
        if (son==fa)    continue;
        Dfs1(son,x);
        Size[x]+=Size[son];
        if (!Heavy[x]||Size[son]>Size[Heavy[x]])
            Heavy[x]=son;
    }
}
void HLD::Dfs2(int x, int fa){
    if (!x) return;
    _Dfn[Dfn[x]=++Time]=x;
    Top[x]=x==Heavy[fa]?Top[fa]:x;
    Dfs2(Heavy[x],x);
    for (int p=now[x];p;p=pre[p]){
        int son=child[p];
        if (son==fa||son==Heavy[x]) continue;
        Dfs2(son,x);
    }
}
void HLD::solve(int x, int y, int n){
    Xor_Line Ans;
    while (Top[x]!=Top[y]){
        if (Deep[Top[x]]Deep[y])    swap(x,y);
    ST.Query(1,1,n,Dfn[x],Dfn[y],Ans);
    printf("%lld\n",Ans.Max());
}

int main(){
    int n=read(0),m=read(0);
    for (int i=1;i<=n;i++)  V[i]=read(0ll);
    for (int i=1;i
数据结构线段树Source各省省选数据结构树链剖分数学线性基

相关

标签