BZOJ4568: [Scoi2016]幸运数字(线性基 倍增)
程序员文章站
2022-05-30 21:58:18
题意 "题目链接" Sol 线性基是可以合并的 倍增维护一下 然后就做完了?? 喵喵喵? cpp // luogu judger enable o2 include define LL long long using namespace std; const int MAXN = 2e4 + 10, ......
题意
sol
线性基是可以合并的
倍增维护一下
然后就做完了??
喵喵喵?
// luogu-judger-enable-o2 #include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 2e4 + 10, b = 60; inline ll read() { char c = getchar(); ll x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, q, g[maxn][16], dep[maxn]; ll a[maxn]; vector<int> v[maxn]; struct node { ll p[62]; node() { memset(p, 0, sizeof(p)); } void insert(ll x) { for(int i = b; i >= 0; i--) { if((!(x >> i & 1))) continue; if(p[i]) {x ^= p[i]; continue;} p[i] = x; break; } } ll querymax() { ll ans = 0; for(int i = b; i >= 0; i--) ans = max(ans, ans ^ p[i]); return ans; } node operator + (const node &rhs) const { node ans; for(int i = 0; i <= b; i++) ans.p[i] = this -> p[i]; for(int i = 0; i <= b; i++) if(rhs.p[i]) ans.insert(rhs.p[i]); return ans; } }f[maxn][16]; void dfs(int x, int fa) { dep[x] = dep[fa] + 1; g[x][0] = fa; f[x][0].insert(a[x]); f[x][0].insert(a[fa]); for(int i = 0; i < v[x].size(); i++) { int to = v[x][i]; if(to == fa) continue; dfs(to, x); } } void pre() { for(int j = 1; j <= 15; j++) for(int i = 1; i <= n; i++) g[i][j] = g[g[i][j - 1]][j - 1], f[i][j] = f[i][j - 1] + f[g[i][j - 1]][j - 1]; } ll query(int x, int y) { node base; base.insert(a[x]); base.insert(a[y]); if(dep[x] < dep[y]) swap(x, y); for(int i = 15; i >= 0; i--) if(dep[g[x][i]] >= dep[y]) base = base + f[x][i], x = g[x][i]; if(x == y) return base.querymax(); for(int i = 15; i >= 0; i--) if(g[x][i] != g[y][i]) { base = base + f[x][i]; base = base + f[y][i]; x = g[x][i], y = g[y][i]; } base = base + f[x][0]; base = base + f[y][0]; return base.querymax(); } int main() { #ifndef online_judge //freopen("a.in", "r", stdin); freopen("b.out", "w", stdout); #endif n = read(); q = read(); for(int i = 1; i <= n; i++) a[i] = read(); for(int i = 1; i <= n - 1; i++) { int x = read(), y = read(); v[x].push_back(y); v[y].push_back(x); } dfs(1, 0); pre(); while(q--) { int x = read(), y = read(); printf("%lld\n", query(x, y)); } return 0; } /* 8 4 45654 251 321 54687 321321 654 6321432 5646 1 2 2 3 2 4 1 5 4 6 6 7 5 8 7 8 7 5 6 8 4 1 */
上一篇: 历史上第一神射手不是李广,是楚国的养由基