Graph
题意思路代码
题意
给定一棵无根树，每条边都有边权。允许删边和增边，但是需要保证图联通并且出现的任何一个环的异或和为
0
0
0。求最小生成树。
思路
看到异或和，可以联想到异或生成树。考虑在点
u
u
u和点
v
v
v之间连一条边，这条边的边权要保证环上边权异或和为
0
0
0。假设
u
u
u和
v
v
v的lca为
r
t
rt
rt，那么我们可以将环分成三部分：从
u
u
u到
r
t
rt
rt，从
v
v
v到
r
t
rt
rt以及新连的边。更进一步，我们可以将
u
u
u到
r
t
rt
rt拓展到
u
u
u到根节点，从
v
v
v到
r
t
rt
rt拓展到
v
v
v到根节点。显然，根节点、
u
u
u、
v
v
v这个大环上边权异或和也为
0
0
0。 所以，我们可以定义
a
i
a_i
ai为
i
i
i节点到根节点路径的异或和。那么，
u
u
u和
v
v
v之间的边的边权即为
a
u
a_u
au ^
a
v
a_v
av。 这样问题就转化为了求这个图的最小异或生成树了。我们可以先通过树形dp的方式求出
a
i
a_i
ai，然后再套一个最小异或生成树的板子，这题就能ac了。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std
;
typedef long long ll
;
const ll inf
= 1e17;
const int N
= 100010, M
= 2 * N
;
int n
;
int a
[N
];
int h
[N
], e
[M
], ne
[M
], idx
;
ll w
[M
];
void add(int aa
,int b
,ll c
)
{
e
[idx
] = b
, w
[idx
] = c
, ne
[idx
] = h
[aa
], h
[aa
] = idx
++;
}
struct XorTrie
{
int dfn
= 0;
int t
[N
*30][2];
int L
[N
*30],R
[N
*30];
void _init()
{
dfn
= 0;
}
void Insert(ll x
,int id
)
{
int rt
= 0;
for(int k
=32;k
>=0;k
--){
int op
= (x
>>k
&1ll)?1:0;
if(!t
[rt
][op
]) t
[rt
][op
] = ++dfn
;
rt
= t
[rt
][op
];
if(!L
[rt
]) L
[rt
] = id
;
R
[rt
] = id
;
}
}
ll
AnswerPos(int rt
,int pos
,ll x
)
{
ll ans
= 0;
for(int i
=pos
;i
>=0;i
--){
int op
= (x
>>i
&1ll)?1:0;
if(t
[rt
][op
]) rt
= t
[rt
][op
];
else{
rt
= t
[rt
][!op
];
ans
+= (1ll<<i
);
}
}
return ans
;
}
void Traceback(int rt
)
{
printf("%d %d\n",L
[rt
],R
[rt
]);
if(t
[rt
][0]) Traceback(t
[rt
][0]);
if(t
[rt
][1]) Traceback(t
[rt
][1]);
}
ll
Divide(int rt
,int pos
)
{
if(t
[rt
][0]&&t
[rt
][1]){
int x
= t
[rt
][0],y
= t
[rt
][1];
ll minl
= inf
;
for(int k
=L
[x
];k
<=R
[x
];k
++) minl
= min(minl
,AnswerPos(y
,pos
-1,a
[k
])+(1ll<<pos
));
return minl
+Divide(t
[rt
][0],pos
-1)+Divide(t
[rt
][1],pos
-1);
}
else if(t
[rt
][0]) return Divide(t
[rt
][0],pos
-1);
else if(t
[rt
][1]) return Divide(t
[rt
][1],pos
-1);
return 0;
}
}trie
;
void dfs(int u
,int fa
)
{
for(int i
=h
[u
];~i
;i
=ne
[i
]){
int j
= e
[i
];
if(j
== fa
) continue;
a
[j
] = a
[u
] ^ w
[i
];
dfs(j
,u
);
}
}
int main()
{
trie
._init();
scanf("%d",&n
);
memset(h
,-1,sizeof(h
));
for(int i
=0;i
<n
-1;i
++){
int aa
,b
;
ll c
;
scanf("%d%d%lld",&aa
,&b
,&c
);
aa
++, b
++;
add(aa
,b
,c
), add(b
,aa
,c
);
}
dfs(1,-1);
sort(a
+1,a
+1+n
);
for(int i
=1;i
<=n
;i
++) trie
.Insert(a
[i
],i
);
printf("%lld\n",trie
.Divide(0,32));
return 0;
}
