欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

[SCOI2016] 幸运数字

程序员文章站 2022-05-02 23:43:57
利用线性基的合并,(直接暴力合并,复杂度62^2),当树上路径和来做。。。(然后跑的巨慢,但是可以优化哈哈) cpp include using namespace std; const int N=2e4+7; struct ShanHenKi { // 胡乱拼的 long long base[6 ......

利用线性基的合并,(直接暴力合并,复杂度62^2),当树上路径和来做。。。(然后跑的巨慢,但是可以优化哈哈)

#include <bits/stdc++.h>
using namespace std;

const int n=2e4+7;

struct shanhenki { // 胡乱拼的
    long long base[64];
    inline bool insert(long long vec) {
        for(int i=62; ~i; --i) {
            if(!(vec>>i)) continue;
            if(!base[i]) {base[i]=vec; return 1;}
            vec^=base[i];
        }
        return 0;
    }
    inline shanhenki add(const shanhenki& d) {
        shanhenki res=*this;
        for(int i=62; ~i; --i) {
            if(d.base[i]) res.insert(d.base[i]);
        }
        return res;
    }
    inline long long max() {
        long long res=0;
        for(int i=62; ~i; --i) {
            if((res^base[i])>res) res^=base[i];
        }
        return res;
    }
} dis[n][20];

int n,m;
int fa[n][20],dep[n];
vector<int> e[n];

void pre(int x,int pa) {
    dep[x]=dep[fa[x][0]=pa]+1;
    for(int i=1; (1<<i)<=dep[x]; ++i) {
        fa[x][i]=fa[fa[x][i-1]][i-1];
        dis[x][i]=dis[x][i-1].add(dis[fa[x][i-1]][i-1]);
    }
    for(int y:e[x]) if(y!=pa) {
        pre(y,x);
    }
}
long long query(int x,int y) {
    shanhenki res;
    memset(&res,0,sizeof res);
    if(dep[x]<dep[y]) swap(x,y);
    int dif=dep[x]-dep[y];
    for(int i=19; ~i; --i) {
        if(dif&(1<<i)) {
            res=res.add(dis[x][i]), x=fa[x][i];
        }
    }
    if(x==y) return res.add(dis[x][0]).max();
    for(int i=19; ~i; --i) {
        if(fa[x][i]!=fa[y][i]) {
            res=res.add(dis[x][i]), x=fa[x][i];
            res=res.add(dis[y][i]), y=fa[y][i];
        }
    }
    res=res.add(dis[x][0]).add(dis[y][1]);
    return res.max();
}

int main() {
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i) {
        long long x;
        scanf("%lld",&x);
        dis[i][0].insert(x);
    }
    for(int i=n,x,y; --i; ) {
        scanf("%d%d",&x,&y);
        e[x].push_back(y);
        e[y].push_back(x);
    }
    pre(1,0);
    for(int i=m,x,y; i--; ) {
        scanf("%d%d",&x,&y);
        printf("%lld\n",query(x,y));
    }
    return 0;
}