[SCOI2016]幸运数字

题目描述

A 国共有 n 座城市，这些城市由 n-1 条道路相连，使得任意两座城市可以互达，且路径唯一。每座城市都有一个幸运数字，以纪念碑的形式矗立在这座城市的正中心，作为城市的象征。

一些旅行者希望游览 A 国。旅行者计划乘飞机降落在 x 号城市，沿着 x 号城市到 y 号城市之间那条唯一的路径游览，最终从 y 城市起飞离开 A 国。在经过每一座城市时，游览者就会有机会与这座城市的幸运数字拍照，从而将这份幸运保存到自己身上。然而，幸运是不能简单叠加的，这一点游览者也十分清楚。他们迷信着幸运数字是以异或的方式保留在自己身上的。

例如，游览者拍了 3 张照片，幸运值分别是 5，7，11，那么最终保留在自己身上的幸运值就是 9（5 xor 7 xor 11）。

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

输入输出格式

输入格式：

第一行包含 2 个正整数 n ，q，分别表示城市的数量和旅行者数量。

第二行包含 n 个非负整数，其中第 i 个整数 Gi 表示 i 号城市的幸运值。

随后 n-1 行，每行包含两个正整数 x ，y，表示 x 号城市和 y 号城市之间有一条道路相连。

随后 q 行，每行包含两个正整数 x ，y，表示这名旅行者的旅行计划是从 x 号城市到 y 号城市。N<=20000,Q<=200000,Gi<=2^60

输出格式：

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

输入输出样例

输入样例#1：

4 2

11 5 7 9

1 2

1 3

1 4

2 3

1 4

输出样例#1：

14

11

很神的题目，思路还是比较好想的，倍增套上线性基，但是代码还是不怎么好写，而且貌似我的常数比较大。倍增预处理的时候暴力合并线性基，倍增找lca的时候也暴力合并即可。

#include<bits/stdc++.h>

#define lll long long

using namespace std;

lll read(){

    lll x=0,w=1;char ch=getchar();

    while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*w;

}

const lll N=20010;

lll n,q,x,y,cnt,qwe;

lll head[N],c[63][21][N],f[21][N],ans[63],deep[N],a[N];

struct node{

    lll to,next;

}edge[2*N];

void add(lll x,lll y){

    cnt++;edge[cnt].to=y;edge[cnt].next=head[x];head[x]=cnt;

}

void insert(lll opt,lll k,lll v){

    for(lll i=61;i>=0;i--){

        if(!(v>>i))continue;

        if(!c[i][opt][k]){c[i][opt][k]=v;break;}

        v^=c[i][opt][k];if(!v)break;

    }

}

void dfs(lll k,lll fa){

    for(lll i=head[k];i;i=edge[i].next){

        lll v=edge[i].to;if(v==fa)continue;

        deep[v]=deep[k]+1;f[0][v]=k;insert(0,v,a[k]);

        dfs(v,k);

    }

}

void merge(lll k,lll opt,lll v1,lll v2){

    for(lll i=61;i>=0;i--)c[i][opt][k]=c[i][opt-1][v1];

    for(lll i=61;i>=0;i--){

        if(c[i][opt-1][v2])insert(opt,k,c[i][opt-1][v2]);

    }

}

void init(){

    for(lll i=1;i<=19;i++){

        for(lll j=1;j<=n;j++){

            f[i][j]=f[i-1][f[i-1][j]];

            merge(j,i,j,f[i-1][j]);

        }

    }

}

void update(lll opt,lll k){

    for(lll j=61;j>=0;j--){

        if(c[j][opt][k]){

            lll v=c[j][opt][k];

            for(lll i=61;i>=0;i--){

                if(!(v>>i))continue;

                if(!ans[i]){ans[i]=v;break;}

                v^=ans[i];if(!v)break;

            }

        }

    }

}

void LCA(lll x,lll y){

    memset(ans,0,sizeof(ans));

    lll v=a[x];

    for(lll i=61;i>=0;i--){

        if(!(v>>i))continue;

        if(!ans[i]){ans[i]=v;break;}

        v^=ans[i];if(!v)break;

    }

    v=a[y];

    for(lll i=61;i>=0;i--){

        if(!(v>>i))continue;

        if(!ans[i]){ans[i]=v;break;}

        v^=ans[i];if(!v)break;

    }

    if(deep[x]<deep[y])swap(x,y);

    for(lll i=19;i>=0;i--){

        if(deep[f[i][x]]>=deep[y]){

            update(i,x);

            x=f[i][x];

        }

    }

    if(x==y)return;

    for(lll i=19;i>=0;i--){

        if(f[i][x]!=f[i][y]){

            update(i,x);update(i,y);

            x=f[i][x];y=f[i][y];

        }

    }

    //cout<<f[0][x]<<endl;

    update(0,x);return;

}

int main(){

    n=read();q=read();

    for(lll i=1;i<=n;i++)a[i]=read();

    for(lll i=1;i<n;i++){

        x=read();y=read();

        add(x,y);add(y,x);

    }

    deep[1]=1;dfs(1,0);init();

    while(q--){

        x=read();y=read();

        LCA(x,y);qwe=0;

        for(lll i=61;i>=0;i--){

            if(qwe<(qwe^ans[i]))qwe^=ans[i];

        }printf("%lld\n",qwe);

    }

}

巴特西

[SCOI2016]幸运数字（线性基，倍增）

[SCOI2016]幸运数字

题目描述

输入输出格式

输入输出样例

最新文章

热门文章