bzoj4568 [Scoi2016]幸運數字（LCA+線性基）

題目連結

分析：

學長說這叫：樹上線性基

有多重做法

（1）樹鍊剖分+線性基合并（2）LCA+倍增+線性基合并（3）點分治+線性基合并

後兩個是 logn l o g n 級的，第一種是 log2n l o g 2 n 級的

就代碼複雜度來說，當然是選擇第二種方法啦

每個結點維護向上跳 2i 2 i 步經過的數字的線性基

線性基的合并直接暴力即可

最後的統計答案就是普通的線性基求異或和最大

tip

我在倍增的時候沒有線上性基中插入該點的權值

是以在詢問的時候，需要單獨加入兩端點的權值：

A.insert(val[x]); A.insert(val[y]);

LCA不要寫錯了，不然WA的太冤

#include<bits/stdc++.h> 
#define ll long long

using namespace std;

const int N=;
struct po{
    ll b[];
    void clear() {
        memset(b,,sizeof(b));
    }
    void insert(ll x) {
        for (int i=;i>=;i--)
            if (x>>i&) {
                if (b[i]) x^=b[i];
                else {
                    b[i]=x;
                    break;
                }
        }
    }
    void Insert(po B) {
        for (int i=;i>=;i--) 
            if (B.b[i])
                insert(B.b[i]);
    }
};
po a[N][];
struct node{
    int y,nxt;
};
node way[N<<];
int st[N],tot=,n,m,pre[N][],deep[N],lg;
ll val[N];

void add(int u,int w) {
    tot++;way[tot].y=w;way[tot].nxt=st[u];st[u]=tot;
    tot++;way[tot].y=u;way[tot].nxt=st[w];st[w]=tot;
}

void dfs(int now,int fa,int dep) {
    pre[now][]=fa;
    deep[now]=dep;
    a[now][].insert(val[fa]);
    for (int i=st[now];i;i=way[i].nxt)
        if (way[i].y!=fa)
            dfs(way[i].y,now,dep+); 
}

void prepare() {
    dfs(,,);

    lg=log(n)/log();
    for (int i=;i<=lg;i++)
        for (int j=;j<=n;j++) {
            pre[j][i]=pre[pre[j][i-]][i-];
            a[j][i]=a[j][i-];
            a[j][i].Insert(a[pre[j][i-]][i-]);
        }
}

void solve(int x,int y) {
    po A; A.clear();
    A.insert(val[x]); A.insert(val[y]);

    if (deep[x]<deep[y]) swap(x,y);
    int d=deep[x]-deep[y];
    if (d) 
        for (int i=;i<=lg&&d;i++,d>>=) 
            if (d&) {
                A.Insert(a[x][i]);
                x=pre[x][i];
            }
    if (x!=y) {
        for (int i=lg;i>=;i--)
            if (pre[x][i]!=pre[y][i]) {
                A.Insert(a[x][i]);
                A.Insert(a[y][i]);
                x=pre[x][i];
                y=pre[y][i];
            }
        A.insert(val[pre[x][]]);
    }

    ll ans=;
    for (int i=;i>=;i--)
        if (A.b[i]&&((ans^A.b[i])>ans))
            ans^=A.b[i];
    printf("%lld\n",ans);
}

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=;i<=n;i++) 
        scanf("%lld",&val[i]);
    for (int i=;i<n;i++) {
        int u,w;
        scanf("%d%d",&u,&w);
        add(u,w);
    }
    prepare();
    for (int i=;i<=m;i++) {
        int x,y;
        scanf("%d%d",&x,&y);
        solve(x,y);
    }
    return ;
}