Join Us
Loading Similar Posts
Entering edit mode
//k-xor tree
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
ll n;cin >> n;
for(ll i=0;i<n-1;i++) {
ll a,b;cin >> a >> b;
}
ll sum=0;
vector<ll> temp;
for(ll i=0;i<n;i++) {
ll var;cin >> var;
temp.push_back(var);
}
ll k;cin >> k;
vector<ll> v;
for(auto var:temp) {
v.push_back((var^k)-var);
sum+=var;
}
sort(v.begin(), v.end(), greater<ll>());
ll i=1;
while(i<n) {
if(v[i]<0) {
if(v[i-1]>0) {
if(v[i-1]>-v[i]) sum+=v[i]+v[i-1];
}
break;
}
sum+=v[i]+v[i-1];
i+=2;
}
cout << sum << "\n";
return 0;
}
Hi can you please explain the code it would be of great help
property of xor: a xor b xor b = a. (because b xor b = 0)
we can only perform xor operation on even no of nodes that raises 2 cases.
case1: when the number of nodes are odd you can't perform xor operation on all elements, one element will be left out even if its value increases after xor operation.
case2: since not all values increase after xor operation you would ideally want to not perform xor operation on those values that decrease after xor operation. But since we can only perform xor on even number of nodes there will be a case when u have to choose between taking a value that decreases after operation or leaving a value that increases after operation.
property of xor: a xor b xor b = a. (because b xor b = 0)
we can only perform xor operation on even no of nodes that raises 2 cases.
case1: when the number of nodes are odd you can't perform xor operation on all elements, one element will be left out even if its value increases after xor operation.
case2: since not all values increase after xor operation you would ideally want to not perform xor operation on those values that decrease after xor operation. But since we can only perform xor on even number of nodes there will be a case when u have to choose between taking a value that decreases after operation or leaving a value that increases after operation.