題目描述

A 國共有 n 座城市，這些城市由 n-1 條道路相連，使得任意兩座城市可以互達，且路徑唯一。每座城市都有一個幸運數字，以紀念碑的形式矗立在這座城市的正中心，作為城市的象征。

一些旅行者希望游覽 A 國。旅行者計劃乘飛機降落在 x 號城市，沿著 x 號城市到 y 號城市之間那條唯一的路徑游覽，最終從 y 城市起飛離開 A 國。在經過每一座城市時，游覽者就會有機會與這座城市的幸運數字拍照，從而將這份幸運保存到自己身上。然而，幸運是不能簡單疊加的，這一點游覽者也十分清楚。他們迷信著幸運數字是以異或的方式保留在自己身上的。

例如，游覽者拍了 3 張照片，幸運值分別是 5，7，11，那么最終保留在自己身上的幸運值就是 9（5 xor 7 xor 11）。

有些聰明的游覽者發現，只要選擇性地進行拍照，便能獲得更大的幸運值。例如在上述三個幸運值中，只選擇 5 和 11 ，可以保留的幸運值為 14 ?，F在，一些游覽者找到了聰明的你，希望你幫他們計算出在他們的行程安排中可以保留的最大幸運值是多少。

輸入輸出格式

輸入格式：

第一行包含 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

思路：

題意本質是給出一棵點帶權的樹，q 次詢問，每次詢問從 x 到 y 路徑上的點中選擇一些點使得他們的權值異或和最大，輸出最大異或和

要求權值異或和最大，明顯可以使用線性基來解決，問題在于多次詢問，每次求一條路徑上的線性基

利用倍增求 LCA 進行預處理，開一個結構體 node，用 node[i][j].x 來表示 i 點向上跳 2^j 個點能到達的祖先，node[i][j].d 表示 i 點到 node[i][j].x 的路徑上所有點的權值的線性基

這樣一來，在詢問 x 到 y 上的最大異或和時，將 x 到 LCA(x,y) 與 y 到 LCA(x,y) 的線性基合并即可

源代碼

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define EPS 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long #define Pair pair<int,int> const int MOD = 2008; const int N = 20000+5; const int dx[] = {0,0,-1,1,-1,-1,1,1}; const int dy[] = {-1,1,0,0,-1,1,-1,1}; using namespace std;struct LinearBasis {int x;//點xLL d[60+5];//線性基LinearBasis() {memset(d,0,sizeof(d));}bool add(LL x) {for(int i=60; i>=0; i--) {if(x&(1LL<<i)) {if(d[i])//插入失敗，異或x^=d[i];else {//插入成功，保存后退出d[i]=x;break;}}}return x>0;//x>0插入成功}LL queryMax() {//查詢最大值LL res=0;for(int i=60; i>=0; i--)if((res^d[i])>res)res^=d[i];return res;} } lb[N][20];//倍增數組 struct Edge{int to;int next; }edge[N<<1]; int head[N],tot; int n,m; LL a[N]; int deep[N]; void addEdge(int x,int y) {edge[++tot].to=y;edge[tot].next=head[x];head[x]=tot; } void LCA(int x) {//處理倍增數組初值for(int i=head[x]; i; i=edge[i].next) {int y=edge[i].to;if(y==lb[x][0].x)continue;lb[y][0].x=x;lb[y][0].add(a[x]);//將x的權值加入到lb[y][0]的線性基lb[y][0].add(a[y]);//將y的權值加入到lb[y][0]的線性基deep[y]=deep[x]+1;LCA(y);} } LL query(int x,int y) {LinearBasis res;if(deep[x]!=deep[y]) {if(deep[x]>deep[y])swap(x,y);for(int j=14; j>=0; j--) {if(deep[lb[y][j].x]>=deep[x]) {for(int k=60; k>=0; k--) //沿途記錄線性基if(lb[y][j].d[k]!=0)res.add(lb[y][j].d[k]);y=lb[y][j].x;}}}for(int j=14; j>=0; j--){if(lb[x][j].x!=lb[y][j].x) {for(int k=60; k>=0; k--) {if(lb[x][j].d[k]!=0)res.add(lb[x][j].d[k]);if(lb[y][j].d[k]!=0)res.add(lb[y][j].d[k]);}x=lb[x][j].x;y=lb[y][j].x;}}if(x!=y) {for(int k=60; k>=0; k--) {if(lb[x][0].d[k]!=0)res.add(lb[x][0].d[k]);if(lb[y][0].d[k]!=0)res.add(lb[y][0].d[k]);}}return res.queryMax(); } int main() {scanf("%d%d",&n,&m);for(int i=1; i<=n; i++)scanf("%lld",&a[i]);for(int i=1; i<n; i++) {int x,y;scanf("%d %d",&x,&y);addEdge(x,y);addEdge(y,x);}deep[1]=1;LCA(1);for(int j=1; j<=14; j++){for(int i=1; i<=n; i++) { //求倍增數組lb[i][j].x=lb[lb[i][j-1].x][j-1].x;for(int k=0; k<=60; k++) //將lb[i][j-1].d和lb[lb[i][j-1]][j-1].d合并起來成lb[i][j].dlb[i][j].d[k]=lb[i][j-1].d[k];for(int k=0; k<=60; k++)if(lb[lb[i][j-1].x][j-1].d[k]!=0)lb[i][j].add(lb[lb[i][j-1].x][j-1].d[k]);}}for(int i=1; i<=m; i++) {int x,y;scanf("%d%d",&x,&y);LL res;if(x==y)//特判res=a[x];elseres=query(x,y);printf("%lld\n",res);} }

?

總結

以上是生活随笔為你收集整理的幸运数字（洛谷-P3292）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。