异或最小生成树

异或最小生成树

题目大意

$n$个点，每个点有一个点权$a_i$，两点之间$(u,v)$加一条边，则边权为$a_u$^ $a_v$，可以任意加边，求最小生成树。
$n\le 10^5,a_i\le 2^{30}$

思路

点数太多不能把边全造出来所以不能Kruskal。考虑boruvka算法，即对于每一个联通块都选择向外连出的最小边（也就是并行的prim？）。对于异或，容易想到01-trie，高位在上建出trie树，则LCA越深的两个点，连边的代价越小。所以可以天然的将每个点为根的子树作为boruvka算法中的联通块，考虑如果点$x$向下的01都有边，则显然以$x$作为LCA建出一条边是最小的可以连接$x$的两个儿子的联通块的边。所以不断向上合并即可。

• 若一个点有两个儿子01，则从两个儿子开始同时dfs，下面尽量走同向（同时走0或者同时走1）取min，否则加上当前的权值，对走不同向取min。
• 若一个点只有一个儿子，则直接向下走即可，当前点不需要加边。

复杂度，对于每一个点都有可能访问到叶子，$O(nlo{g}^{2}n)$

Codeforces 888G

题目链接
题意：异或最小生成树模板题

#include
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_back

using namespace std;

inline ll read()
{
	ll f=1,sum=0;char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-1;c=getchar();}
	while (isdigit(c)) {sum=sum*10+c-'0';c=getchar();}
	return sum*f;
}
const int MAXN=200010;
const int MAXM=MAXN*30;
int ch[MAXM][2],num=1,sz[MAXM],a[MAXN],rt=1;
void insert(int x)
{
	int now=rt;
	for (int i=29;i>=0;i--)
	{
		int dig=(x>>i)&1;
		if (!ch[now][dig]) ch[now][dig]=++num;
		now=ch[now][dig];
	}
	sz[now]=1;
}
int merge_cost(int rt1,int rt2,int deep)
{
	int ans1=-1,ans2=-1;
	if (ch[rt1][0] && ch[rt2][0]) ans1=merge_cost(ch[rt1][0],ch[rt2][0],deep-1);
	if (ch[rt1][1] && ch[rt2][1]) ans2=merge_cost(ch[rt1][1],ch[rt2][1],deep-1);
	if (ans1!=-1 || ans2!=-1)
	{
		if (ans1==-1) return ans2;
		if (ans2==-1) return ans1;
		return min(ans1,ans2);
	}
	ans1=-1,ans2=-1;
	if (ch[rt1][0] && ch[rt2][1]) ans1=merge_cost(ch[rt1][0],ch[rt2][1],deep-1)+(1<<deep);
	if (ch[rt1][1] && ch[rt2][0]) ans2=merge_cost(ch[rt1][1],ch[rt2][0],deep-1)+(1<<deep);
	if (ans1!=-1 || ans2!=-1)
	{
		if (ans1==-1) return ans2;
		if (ans2==-1) return ans1;
		return min(ans1,ans2);
	}
	return 0;
}
ll ans=0;
void query(int x,int deep)
{
	if (ch[x][0] && ch[x][1]) ans+=(1<<deep)+merge_cost(ch[x][0],ch[x][1],deep-1);
	if (ch[x][0]) query(ch[x][0],deep-1);
	if (ch[x][1]) query(ch[x][1],deep-1);
}
int main()
{
	int n=read();
	for (int i=1;i<=n;i++) a[i]=read(),insert(a[i]);
	query(rt,29);
	cout<<ans<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

2020牛客多校5 B Graph

题目链接
题目大意：
给定一棵树，每条边有边权$W_i$，可以任意次的加边或删边（任意权值），但是要时刻保证：

• 图连通
• 对于每一个环，环上所有边权异或和为0

求最后这张图的最小边权和。$n\le 2\ast 10^5,0\le W_i<2^{30}$

思路：考虑这个时刻保证，也就是说一开始只能加边且加边$(u,v)$的边权只能是这一条路径的异或和，容易推广到后面的情况，也就是说每条边的边权其实都是固定的，所以不妨随意指定一个点的权值，可以直接推出剩下所有点的权值，也就是把边权转化为了点权，边权变为两个点的异或值，也就变成了异或最小生成树。

/*
题目链接：https://ac.nowcoder.com/acm/contest/65437/B
*/

#include
#define pa pair<int,int>
#define INF 0x3f3f3f3f
#define inf 0x3f
#define fi first
#define se second
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define pb push_back

using namespace std;

inline ll read()
{
	ll f=1,sum=0;char c=getchar();
	while (!isdigit(c)) {if (c=='-') f=-1;c=getchar();}
	while (isdigit(c)) {sum=sum*10+c-'0';c=getchar();}
	return sum*f;
}
const int MAXN=100010;
const int MAXM=MAXN*30;
struct edge{
	int next,to,val;
}e[MAXN*2];
int head[MAXN],cnt;
void addedge(int u,int v,int w)
{
	e[++cnt].next=head[u];
	e[cnt].to=v;
	e[cnt].val=w;
	head[u]=cnt;
}
int a[MAXN];
void dfs(int x,int fa)
{
	for (int i=head[x];i;i=e[i].next)
	{
		int v=e[i].to;
		if (v==fa) continue;
		a[v]=e[i].val^a[x];
		dfs(v,x);
	}
}
int ch[MAXM][2],num=1,rt=1;
void insert(int x)
{
	int now=rt;
	for (int i=30;i>=0;i--)
	{
		int dig=(x>>i)&1;
		if (!ch[now][dig]) ch[now][dig]=++num;
		now=ch[now][dig];
	}
}
int merge_cost(int rt1,int rt2,int deep)
{
	int ans1=-1,ans2=-1;
	if (ch[rt1][0] && ch[rt2][0]) ans1=merge_cost(ch[rt1][0],ch[rt2][0],deep-1);
	if (ch[rt1][1] && ch[rt2][1]) ans2=merge_cost(ch[rt1][1],ch[rt2][1],deep-1);
	if (ans1!=-1 || ans2!=-1)
	{
		if (ans1==-1) return ans2;
		if (ans2==-1) return ans1;
		return min(ans1,ans2);
	}
	ans1=-1,ans2=-1;
	if (ch[rt1][0] && ch[rt2][1]) ans1=merge_cost(ch[rt1][0],ch[rt2][1],deep-1)+(1<<deep);
	if (ch[rt1][1] && ch[rt2][0]) ans2=merge_cost(ch[rt1][1],ch[rt2][0],deep-1)+(1<<deep);
	if (ans1!=-1 || ans2!=-1)
	{
		if (ans1==-1) return ans2;
		if (ans2==-1) return ans1;
		return min(ans1,ans2);
	}
	return 0;
}
ll ans;
void query(int x,int deep)
{
	if (ch[x][0] && ch[x][1]) ans+=(1<<deep)+merge_cost(ch[x][0],ch[x][1],deep-1);
	if (ch[x][0]) query(ch[x][0],deep-1);
	if (ch[x][1]) query(ch[x][1],deep-1);
}
int main()
{
	int n=read();
	for (int i=1;i<n;i++)
	{
		int u=read()+1,v=read()+1,w=read();
		addedge(u,v,w),addedge(v,u,w);
	}
	dfs(1,0);
	for (int i=1;i<=n;i++) insert(a[i]);
	query(1,30);
	cout<<ans<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102