题目链接
loj#2013. 「SCOI2016」幸运数字
题解
和树上路径有管...点分治吧 把询问挂到点上 求出重心后，求出重心到每个点路径上的数的线性基 对于重心为lca的合并寻味，否则标记下传 对于每个询问，只需要暴力合并两个线性基即可 每个点只会被加到logn个线性基里，所以总复杂度为O(nlogn60 + q60*2) 然后我写了句memset(b,0,sizeof 0)...被卡了1h...
代码
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
inline int read() {
int x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();
return x * f;
}
inline long long Read() {
long long x = 0,f = 1;
char c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar();
return x * f;
}
#define LL long long
const int maxn = 200007;
int n,m;
long long val[maxn];
struct node {
int v,next;
} edge[maxn << 1];
int head[maxn],num = 0;
inline void add_edge(int u,int v) {
edge[++ num].v = v;edge[num].next = head[u],head[u] = num;
}
struct Base {
LL b[63];
inline void clear() {memset(b,0,sizeof b); }
inline void insert(LL x) {
for(int i = 60;~i;-- i)
if(x >> i & 1)
if(b[i]) x ^= b[i];
else {b[i] = x; break;}
}
inline void merge(const Base &x) {
for(int i = 60;~i;-- i)
if(x.b[i]) insert(x.b[i]);
}
inline LL query() {
LL ret = 0;
for(int i = 60;~i;-- i)
ret = std::max(ret ^ b[i],ret);
return ret;
}
} base[maxn];
int U[maxn],V[maxn],sz[maxn],bel[maxn];
LL ans[maxn];
std::vector<int>q[maxn];
bool vis[maxn];
int root = 0,mt;
void get_root(int x,int fa,int tot) {
sz[x] = 1; int mx = 0;
for(int i = head[x];i;i = edge[i].next) {
int v = edge[i].v;
if(v == fa || vis[v]) continue;
get_root(v,x,tot);
sz[x] += sz[v];
mx = std::max(mx,sz[v]);
}
mx = std::max(tot - sz[x],mx);
if(mx < mt) root = x, mt = mx;
}
void dfs(int x,int fa,int Bel) {
bel[x] = Bel; base[x] = base[fa]; base[x].insert(val[x]);
for(int i = head[x];i;i = edge[i].next)
if(edge[i].v != fa && !vis[edge[i].v])
dfs(edge[i].v,x,Bel);
}
int tq[maxn];
void solve(int x) {
if(!q[x].size()) return;
mt = 20005; get_root(x,x,sz[x]);
vis[root] = 1;
bel[root] = root;
base[root].clear();
base[root].insert(val[root]);
for(int i = head[root];i;i = edge[i].next)
if(!vis[edge[i].v])
dfs(edge[i].v,root,edge[i].v);
int tot = q[x].size();
for(int i = 0;i <= tot;++ i) tq[i] = q[x][i];
q[x].clear();
Base tmp;
for(int i = 0,id;i < tot;++ i) {
if(bel[U[id = tq[i]]] == bel[V[id]])
q[bel[U[id]]].push_back(id);
else
tmp = base[U[id]],
tmp.merge(base[V[id]]),
ans[id] = tmp.query();
}
for(int i = head[root];i;i = edge[i].next)
if(!vis[edge[i].v]) solve(edge[i].v);
}
int main() {
//freopen("lucky1.in","r",stdin);
n = read();m = read();
for(int i = 1;i <= n;++ i) val[i] = Read();
for(int u,v,i = 1;i < n;++ i) {
u = read(),v = read();
add_edge(u,v); add_edge(v,u);
}
for(int i = 1;i <= m;++ i) {
U[i] = read(),V[i] = read();
if(U[i] == V[i]) ans[i] = val[U[i]];
else q[1].push_back(i);
}
sz[1] = n; solve(1);
for(int i = 1;i <= m;++ i)
printf("%lld\n",ans[i]);
return 0;
}
转载于:https://www.cnblogs.com/sssy/p/9574850.html
相关资源：JAVA上百实例源码以及开源项目
