然后发现果然合并有更NB的方法。
不是高斯消元(原谅我zz)，而是应该一个一个插。
终于19sA掉了。
52s
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #define ll long long 6 #define N 20005 7 using namespace std; 8 int read() 9 { 10 int p=0;char c=getchar(); 11 while(c<‘0‘||c>‘9‘)c=getchar(); 12 while(c>=‘0‘&&c<=‘9‘)p=p*10+c-‘0‘,c=getchar(); 13 return p; 14 } 15 int n,m; 16 int head[N],ver[N*2],nxt[N*2],tot; 17 ll mi[N]; 18 void add(int a,int b) 19 { 20 tot++;nxt[tot]=head[a];head[a]=tot;ver[tot]=b;return ; 21 } 22 ll ji[N][16][62]; 23 int fa[N][16],dep[N]; 24 ll a[N]; 25 void dfs(int x,int f) 26 { 27 for(int i=head[x];i;i=nxt[i]) 28 { 29 if(ver[i]==f)continue; 30 fa[ver[i]][0]=x; 31 dep[ver[i]]=dep[x]+1; 32 ji[ver[i]][0][0]=1; 33 ji[ver[i]][0][1]=a[ver[i]]; 34 dfs(ver[i],x); 35 } 36 return ; 37 } 38 ll tmp[182]; 39 void guess() 40 { 41 int k=1;int now=tmp[0]; 42 for(int i=60;i>=0;i--) 43 { 44 int p=0;ll o=mi[i]; 45 for(int j=k;j<=now;j++) 46 { 47 if((tmp[j]&o)) 48 { 49 p=j;break; 50 } 51 } 52 if(p) 53 { 54 swap(tmp[p],tmp[k]); 55 for(int j=1;j<=now;j++) 56 { 57 if(j!=k&&(tmp[j]&o)) 58 { 59 tmp[j]^=tmp[k]; 60 } 61 }k++; 62 } 63 } 64 tmp[0]=k-1; 65 } 66 void yu() 67 { 68 for(int i=1;i<=15;i++) 69 { 70 for(int j=1;j<=n;j++) 71 { 72 tmp[0]=ji[j][i-1][0]+ji[fa[j][i-1]][i-1][0]; 73 for(int k=1;k<=ji[j][i-1][0];k++)tmp[k]=ji[j][i-1][k]; 74 for(int k=1;k<=ji[fa[j][i-1]][i-1][0];k++)tmp[k+ji[j][i-1][0]]=ji[fa[j][i-1]][i-1][k]; 75 guess(); 76 for(int k=0;k<=tmp[0];k++)ji[j][i][k]=tmp[k]; 77 fa[j][i]=fa[fa[j][i-1]][i-1]; 78 } 79 }return ; 80 } 81 void solve(int x,int y) 82 { 83 if(dep[x]<dep[y])swap(x,y); 84 for(int i=15;i>=0;i--) 85 { 86 if(dep[fa[x][i]]>=dep[y]) 87 { 88 for(int j=1;j<=ji[x][i][0];j++)tmp[0]++,tmp[tmp[0]]=ji[x][i][j]; 89 guess(); 90 x=fa[x][i]; 91 } 92 } 93 if(x!=y) 94 { 95 for(int i=15;i>=0;i--) 96 { 97 if(fa[x][i]!=fa[y][i]) 98 { 99 for(int k=1;k<=ji[x][i][0];k++)tmp[0]++,tmp[tmp[0]]=ji[x][i][k]; 100 guess(); 101 for(int k=1;k<=ji[y][i][0];k++)tmp[0]++,tmp[tmp[0]]=ji[y][i][k]; 102 guess(); 103 x=fa[x][i];y=fa[y][i]; 104 } 105 } 106 tmp[0]++;tmp[tmp[0]]=a[fa[x][0]]; 107 tmp[0]++;tmp[tmp[0]]=a[x]; 108 tmp[0]++;tmp[tmp[0]]=a[y]; 109 } 110 else 111 { 112 tmp[0]++,tmp[tmp[0]]=a[x]; 113 } 114 guess(); 115 ll now=0; 116 for(int i=tmp[0];i>=1;i--) 117 { 118 now^=tmp[i]; 119 } 120 printf("%lld\n",now); 121 return ; 122 } 123 int main() 124 { 125 int q; 126 mi[0]=1; 127 for(int i=1;i<=60;i++)mi[i]=mi[i-1]*2; 128 scanf("%d%d",&n,&q); 129 for(int i=1;i<=n;i++) 130 { 131 scanf("%lld",&a[i]); 132 } 133 int t1,t2,t3; 134 for(int i=1;i<n;i++) 135 { 136 t1=read();t2=read(); 137 add(t1,t2);add(t2,t1); 138 } 139 dep[1]=1; 140 ji[1][0][0]=1;ji[1][0][1]=a[1]; 141 dfs(1,-1); 142 yu(); 143 for(int i=1;i<=q;i++) 144 { 145 t1=read();t2=read(); 146 memset(tmp,0,sizeof(tmp)); 147 solve(t1,t2); 148 } 149 return 0; 150 }
19s
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstring> 5 #define ll long long 6 #define N 20005 7 using namespace std; 8 int read() 9 { 10 int p=0;char c=getchar(); 11 while(c<‘0‘||c>‘9‘)c=getchar(); 12 while(c>=‘0‘&&c<=‘9‘)p=p*10+c-‘0‘,c=getchar(); 13 return p; 14 } 15 int n,m; 16 int head[N],ver[N*2],nxt[N*2],tot; 17 ll mi[N]; 18 void add(int a,int b) 19 { 20 tot++;nxt[tot]=head[a];head[a]=tot;ver[tot]=b;return ; 21 } 22 ll ji[N][16][62]; 23 int fa[N][16],dep[N]; 24 ll a[N]; 25 void dfs(int x,int f) 26 { 27 for(int i=head[x];i;i=nxt[i]) 28 { 29 if(ver[i]==f)continue; 30 fa[ver[i]][0]=x; 31 dep[ver[i]]=dep[x]+1; 32 for(int j=60;j>=0;j--) 33 { 34 if(a[ver[i]]&mi[j]) 35 { 36 ji[ver[i]][0][j]=a[ver[i]]; 37 break; 38 } 39 } 40 dfs(ver[i],x); 41 } 42 return ; 43 } 44 ll tmp[61]; 45 void insert(ll x) 46 { 47 for(int i=60;i>=0;i--) 48 { 49 if(x&mi[i]) 50 { 51 if(!tmp[i]) 52 { 53 tmp[i]=x; 54 break; 55 } 56 else x^=tmp[i]; 57 } 58 }return ; 59 } 60 void yu() 61 { 62 for(int i=1;i<=15;i++) 63 { 64 for(int j=1;j<=n;j++) 65 { 66 for(int k=0;k<=60;k++)tmp[k]=ji[j][i-1][k]; 67 for(int k=0;k<=60;k++) 68 { 69 if(ji[fa[j][i-1]][i-1][k])insert(ji[fa[j][i-1]][i-1][k]); 70 } 71 for(int k=0;k<=60;k++)ji[j][i][k]=tmp[k]; 72 fa[j][i]=fa[fa[j][i-1]][i-1]; 73 } 74 }return ; 75 } 76 void solve(int x,int y) 77 { 78 if(dep[x]<dep[y])swap(x,y); 79 for(int i=15;i>=0;i--) 80 { 81 if(dep[fa[x][i]]>=dep[y]) 82 { 83 for(int j=0;j<=60;j++)if(ji[x][i][j])insert(ji[x][i][j]); 84 x=fa[x][i]; 85 } 86 } 87 if(x!=y) 88 { 89 for(int i=15;i>=0;i--) 90 { 91 if(fa[x][i]!=fa[y][i]) 92 { 93 for(int k=0;k<=60;k++)if(ji[x][i][k])insert(ji[x][i][k]); 94 for(int k=0;k<=60;k++)if(ji[y][i][k])insert(ji[y][i][k]); 95 x=fa[x][i];y=fa[y][i]; 96 } 97 } 98 insert(a[fa[x][0]]);insert(a[x]);insert(a[y]); 99 } 100 else 101 { 102 insert(a[x]); 103 } 104 ll now=0; 105 for(int i=60;i>=0;i--) 106 { 107 now=max(now,now^(tmp[i])); 108 } 109 printf("%lld\n",now); 110 return ; 111 } 112 int main() 113 { 114 int q; 115 mi[0]=1; 116 for(int i=1;i<=60;i++)mi[i]=mi[i-1]*2; 117 scanf("%d%d",&n,&q); 118 for(int i=1;i<=n;i++) 119 { 120 scanf("%lld",&a[i]); 121 } 122 int t1,t2,t3; 123 for(int i=1;i<n;i++) 124 { 125 t1=read();t2=read(); 126 add(t1,t2);add(t2,t1); 127 } 128 dep[1]=1; 129 for(int i=60;i>=0;i--) 130 { 131 if(a[1]&mi[i]) 132 { 133 ji[1][0][i]=a[1]; 134 break; 135 } 136 } 137 dfs(1,-1); 138 yu(); 139 for(int i=1;i<=q;i++) 140 { 141 t1=read();t2=read(); 142 memset(tmp,0,sizeof(tmp)); 143 solve(t1,t2); 144 } 145 return 0; 146 }
原文：http://www.cnblogs.com/ezyzy/p/6345110.html