这道题代码虽然比较短，但花了我整整一天才过，太菜了
这是 CF241B 的加强版，但是有点不同，因为 CF241B 后半部分求前 \(k\) 大的和没法优化了，而这道题能把前面的求第 \(k\) 小时间复杂度优化到单 log ，但是需要注意这道题开 trie 完全开不下，所以肯定没法 trie 上二分做到单 log
对于某些二进制的题，只要没顺序影响，一位一位算贡献是可行的。然后对于这道题，我只需要枚举每一位考虑异或出来的是填 0 还是填 1 ，此时假设考虑到了第 \(i\) 位，如果我填 0 能够异或出来符合要求的对数 \(cnt\) 小于 \(k\) 的话，那么我显然是填 1 ，然后是求 \(k-cnt\) ，如果能填0，就填 0 。统计的话不难，对每个元素遍历统计子数内元素个数就行了。
注意统计和算答案都需要对每个元素都搞个指针记录一下，统计完直接分上述两种情况移指针就可以了
然后就会 MLE ，滚动一下 trie ，相当于就是我把普通建立 trie 的循环交换了顺序，就能滚动数组，统计答案只和这一层有关系，需要记录上一层的指针是指 trie 中的哪个节点，每次每个节点就重新往下一层递进，同时预处理下统计的数组就行了，注意要开 long long 。
可能是我写的丑，太菜了，感觉细节多
#include<bits/stdc++.h>
#define il inline
#define maxn 1000001
using namespace std;
typedef long long ll;
template<class T>
il T read(){
char c;T x=0,f=0;
while(!isdigit(c=getchar()))f|=(c=='-');
while(isdigit(c))x=(x*10)+(c^48),c=getchar();
return f?-x:x;
}
int n;
ll k,a[maxn];
int trie[maxn][2],p[maxn],cnt[maxn],tot=1,lst[maxn];
il ll calc(int pos){
ll tmp=0;
for(int i=1;i<=n;i++){
int c=(a[i]>>pos)&1;
if(trie[p[i]][c])tmp+=cnt[trie[p[i]][c]];
}
return tmp;
}
signed main(){
n=read<int>(),k=read<ll>();
for(int i=2;i<=n;i++){
int v=read<int>();ll w=read<ll>();
a[i]=a[v]^w;
}
for(int i=1;i<=n;i++)p[i]=1,lst[i]=1;
ll kth=0;
for(int i=62;i>=0;i--){
//统计当前这个位置，有多少个对数异或为0
for(int j=0;j<=tot;j++)trie[j][0]=trie[j][1]=cnt[j]=0;
tot=1;
for(int j=1;j<=n;j++){
int c=(a[j]>>i)&1;
if(!trie[lst[j]][c])trie[lst[j]][c]=++tot;
lst[j]=trie[lst[j]][c],cnt[lst[j]]++;
}
ll os=calc(i),flag=0;
if(os<k)kth+=(1ll<<i),k-=os,flag=1;
for(int j=1;j<=n;j++){
int c=(a[j]>>i)&1;
if(flag){
if(trie[p[j]][c^1])p[j]=trie[p[j]][c^1];
else p[j]=0;
}
else{
if(trie[p[j]][c])p[j]=trie[p[j]][c];
else p[j]=0;
}
}
}
printf("%lld\n",kth);
return 0;
}