神秘好题！！！
题意
有一个有 个结点的树，根节点是 ；和一个长度为 的序列 。
你可以把序列 任意重排，然后依次令树上点 的点权为 ，使所有点到其树根上的简单路径上经过的点权（包含本身）的异或和的与最大，输出这个值。
题解
我们很容易发现两个性质：
- 如果根节点的点权在二进制下第 位的值为 ，那么答案第 为的值也为 ，因为根到根的路径上第 位的异或和为 。
- 如果根节点的点权二进制下第 为的值为 ，且有一个不为根的点 ，使得 的点权二进制下也为 ，那么答案第 为的值也为 ，因为根到 的路径上第 位的异或和为 。
我们令 为所有满足只有一个点权第 位为 的 的和。我们发现答案其实就是 ，即 中所有只有一个点权第 位为 的 的和，即 为根的答案。
Code：
#include<bits/stdc++.h>
#define rg int
#define fo(i,l,r) for(rg i=(l);i<=(r);i++)
#define dfo(i,r,l) for(rg i=(r);i>=(l);i--)
#define fe(i,x) for(rg i=hd[x];i;i=nex[i])
#define frein freopen("in.txt","r",stdin);
#define freout freopen("out.txt","w",stdout);
#define fre(p) freopen(#p".in","r",stdin),freopen(#p".out","w",stdout);
#define outa(l,r,a) {fo(i,l,r)cout<<a[i]<<" ";cout<<"\n";}
#define BZ cout<<"----------------\n";
#define eb emplace_back
#define ll long long
using namespace std;
int n,a[100005],num[62];
inline void solve(){
cin>>n;
fo(i,1,n){
cin>>a[i];
fo(j,1,60){
if((1ll<<(j-1))&a[i]){
num[j]++;
}
}
}
int pp=0;
fo(i,1,60){
if(num[i]==1){
pp|=(1<<(i-1));
}
}
int ans=0;
fo(i,1,n)ans=max(ans,pp&a[i]);
cout<<ans<<'\n';
}
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr);
int T=1;
// cin>>T;
while(T--)solve();
return 0;
}
最后我们惊奇的发现树的形态与答案无关！！！
暂无评论