【BZOJ 3943】[Usaco2015 Feb] SuperBull

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3943
离线版题目：http://paste.ubuntu.com/23080229/

XOR意义下的位运算生成树

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int N = 2000+9;
const int M = N*32;
const int SGZ = 2;

int n,arr[N],fa[N],to[N],val[N];
LL vout;

namespace Trie{
	int MX[M],MN[M],ch[M][SGZ],cnt,root,NUM,COL,ans_tmp;
	
	inline void init(){
		memset(MX,-1,sizeof(MX));
		memset(MN,-1,sizeof(MN));
		memset(ch,0,sizeof(ch));
		cnt = root = 0;
	}
	
	void Insert(int &w, int t){
		if (!w) w = ++cnt; 
		if (!~MX[w] || MX[w] < COL) MX[w] = COL;
		if (!~MN[w] || MN[w] > COL) MN[w] = COL;
		if (t) Insert(ch[w][(NUM&t)>0],t>>1);  
	}
	
	inline void insert(int num, int col){
		if (!root) root = ++cnt;
		NUM = num, COL = col;
		Insert(ch[root][(num&(1<<30))>0],1<<29);
	}
	
	void Query(int w, int t){
		if (t) {
			int to = ch[w][((NUM&t)>0)^1];
			if (to && (MX[to] != COL || MN[to] != COL)) ans_tmp |= t, Query(to,t>>1);
			else Query(ch[w][(NUM&t)>0],t>>1);
 		} else {
			if (COL != MN[w]) COL = MN[w];
			else COL = MX[w]; 	
		}
	} 
	
	inline pair<int,int> query(int num, int col){
		ans_tmp = 0; NUM = num; COL = col;
		Query(root,1<<30);
		return make_pair(ans_tmp,COL);
	}
};

inline int find(int w){
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp = fa[w], fa[w] = f, w = tmp;
	return f;
}

inline int read(){
	char c=getchar(); int ret=0;
	while (c<'0'||c>'9') c=getchar();
	while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
	return ret; 
}

int main(){
	n = read(); int cnt = n-1;
	for (int i=1;i<=n;i++) arr[i] = read(), fa[i] = i;
	while (cnt) {
		Trie::init(); 
		memset(val,0,sizeof(val));
		for (int i=1;i<=n;i++) Trie::insert(arr[i],find(i));
		for (int i=1;i<=n;i++) {
			pair<int,int> tmp = Trie::query(arr[i],fa[i]);
			if (tmp.first > val[fa[i]]) val[fa[i]] = tmp.first, to[fa[i]] = tmp.second;
		}
		for (int i=1;i<=n;i++) if (to[i] && find(to[i]) != find(i)) 
			vout += val[i], fa[find(i)] = find(to[i]), cnt--;
	}
	printf("%lld\n",vout);
	return 0;
}

不过貌似这个题直接暴力就行了？