题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4568
数据生成器:http://paste.ubuntu.com/23202923/
《浅谈省选的时候还不会线性基的悲伤有多大》
今天重新看了一看,结果最开始写的是链剖,T到死 ←是男人就去ZGS的OJ上测,单点时限
后来重新写了LCA的版本,又T到死
于是暴力优化常数,最终5.9s勉强卡过
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 20000+9; int n,q,head[N],nxt[N*2],to[N*2]; LL arr[N]; inline int read(){char c=getchar(); int ret=0;while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret;} inline LL readL(){char c=getchar(); LL ret=0; while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}return ret;} inline void Add_Edge(int u, int v) { static int T = 0; to[++T] = v; nxt[T] = head[u]; head[u] = T; to[++T] = u; nxt[T] = head[v]; head[v] = T; } namespace LCA{ int fa[N][16],dep[N]; LL f[N][16][61],POW[61]; void DFS(int w, int f) { fa[w][1] = f; fa[w][0] = w; dep[w] = dep[f] + 1; for (int i=head[w];i;i=nxt[i]) if (to[i] != f) DFS(to[i],w); } inline void DFS(){DFS(1,1);for (int i=0;i<=60;i++) POW[i] = 1LL<<i;} inline void merge(LL *a, LL *b) { for (int i=60;~i;i--) if (b[i]) { LL w = b[i]; for (int j=60;~j;j--) if (w&POW[j]) { if (!a[j]) {a[j] = w; break;} else w ^= a[j]; } } } inline void init() { for (int j=1;j<=n;j++) for (int i=60;~i;i--) if (POW[i]&arr[j]) {f[j][0][i] = arr[j]; break;} for (int i=1;i<=n;i++) memcpy(f[i][1],f[i][0],sizeof(f[i][0])), merge(f[i][1],f[fa[i][1]][0]); for (int i=1;i<=n;i++) for (int j=2;j<=15;j++) fa[i][j] = fa[fa[i][j-1]][j-1], memcpy(f[i][j],f[i][j-1],sizeof(f[i][j])), merge(f[i][j],f[fa[i][j-1]][j-1]); } inline LL query(int x, int y) { static LL bas[61]; memset(bas,0,sizeof(bas)); if (dep[x] < dep[y]) swap(x,y); for (int i=15;~i;i--) if (dep[fa[x][i]] > dep[y]) merge(bas,f[x][i]), x = fa[fa[x][i]][1]; if (x == y) merge(bas,f[x][0]); else { for (int i=15;~i;i--) if (fa[x][i] != fa[y][i]) merge(bas,f[x][i]), merge(bas,f[y][i]), x = fa[fa[x][i]][1], y = fa[fa[y][i]][1]; merge(bas,f[x][0]); } LL ret = 0; for (int i=0;i<=60;i++) if (bas[i]) for (int j=i+1;j<=60;j++) if (bas[j]&POW[i]) bas[j] ^= bas[i]; for (int i=0;i<=60;i++) ret ^= bas[i]; return ret; } }; int main(){ n = read(); q = read(); for (int i=1;i<=n;i++) arr[i] = readL(); for (int i=1;i<n;i++) Add_Edge(read(),read()); LCA::DFS(); LCA::init(); for (int i=1;i<=q;i++) printf("%lld\n",LCA::query(read(),read())); return 0; }
另外,%Claris,直接上点分治:http://www.cnblogs.com/clrs97/p/5451814.html
I’ll right away take hold of your rss as I can not in finding your e-mail subscription hyperlink or newsletter service. Do you’ve any? Please allow me understand in order that I may just subscribe. Thanks.
You are a very capable individual!