CF1055F Tree and XOR

这道题代码虽然比较短，但花了我整整一天才过，太菜了

这是 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;
}