前提知识:lca求最近公共祖先(倍增)
因为或运算越多值就越大,好像跟上一个相反,所以满足单调不降
要点1:利用数组来对每个点到其祖先节点的或和进行计算(倍增)
要点2:分别对左右两边进行分析到lca点,这样确保无误
要点3:因为满足单调不降,所以遇到大于的节点对左边才有意义
最后,提一点思路:右边v->w(lca),w->z;左边u->z(意义同上);
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N = 2e5 + 10;
int a[N];
vector<int> g[N];
int d[N],fa[N][22], st[N][22];
void dfs(int u, int father) {
d[u] = d[father] + 1; fa[u][0] = father;
st[u][0] = a[father];//st从u点到根节点的或和(不包括u点)
for (int i = 1; i <= 19; i++) {
fa[u][i] = fa[fa[u][i - 1]][i - 1];
st[u][i] = st[fa[u][i - 1]][i - 1] | st[u][i - 1];//注意st里是fa[u][i-1],而不是st[u][i-1],因为st是或值,不是节点了
}
for (int v:g[u]) {
if (v == father) continue;
dfs(v, u);
}
};
int lca(int u, int v) {//寻找最近公共祖先
if (d[u] < d[v]) swap(u, v);
for (int i = 19; i>=0; i--) {
if (d[fa[u][i]] >= d[v]) u = fa[u][i];//注意d里面的内容,不要误写成u了
}
if (u == v) return u;
for (int i = 19; i >= 0; i--) {
if (fa[u][i]!= fa[v][i])
u = fa[u][i], v = fa[v][i];//注意,当时把v写成u死活过不了
}
return fa[u][0];
}
int find(int u,int v){//u到v点的或和,只要保证v为最浅的就不用swap了
int ans=a[u];
for(int i=19;i>=0;i--){
if(d[fa[u][i]]>=d[v])
ans|=st[u][i],u=fa[u][i];
}
return ans;
}
int qry(int u, int v) {
int w = lca(u, v), num = a[u], cnt = __builtin_popcount(num);//库函数,计算数字二进制位1的个数
int x=find(v,w),ans=0;//获得另一边到最近公共祖先的值
while(d[u]>=d[w]){//到达最近公共祖先就退出,表示左边或者右边已经完毕
ans=max(ans,cnt+__builtin_popcount(x|find(u,w)));//求最大,右边点到左边某点的或和
for(int i=19;i>=0;i--)
if(__builtin_popcount(num|st[u][i])==cnt)//相等说明左边的没有变化,没变化往前走(但可导致右边的或和发生变化,所以只要两边都分别进行计算,就不会有遗漏了)
num|=st[u][i],u=fa[u][i];
num|=st[u][0],u=fa[u][0];//更新左节点的位置
cnt=__builtin_popcount(num);//计算左边当前的或和
}
return ans;
}
void solve() {
int n;
cin>>n;
for (int i = 1; i <= n; i++) cin>>a[i];
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
dfs(1, 0);//lca倍增
int q;
cin >> q;
while (q--) {
int u, v;
cin >> u >> v;
cout << max(qry(u, v), qry(v, u))<<' ';//输出两者的最大值(从右往左,或者从左往右)
}
cout << '\n';
for(int i=1;i<=n;i++) g[i].clear();//及时清除
}
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}