Xor-MST学习/ 2020牛客暑假多校(五)B.Graph
题目大意:
给一个完全图,求异或最小生成树。
题解:
首先先看一下这道题:CF888G 。与本题不同之处是这两个题一个给点的权值,一个给边的权值。但实际上一样可以相互转换。如让本题中a[1]= 0,跑一下dfs,算出所有点的权值就变为CF888G题了。
处理异或,考虑使用Trie树。Trie树除了可以处理字符串外,还可以处理二进制。把点值插入Trie树,会发现,两个叶子节点的LCA越深,则它们代表的值的异或值越小(LCA相等时情况不一定)。 要使异或值最小就要尽量让高位相等,尽量走同一条路径。
所以我们计算每一个子树的贡献,考虑启发式合并,每次做siz小的一边在字典树上取计算siz大的一边的贡献。复杂度O(nlogn)。总复杂度(O(nlog^{2}n))
其实把CF888G那题当作一个Xor-MST模板题学会,这一题就直接是套路题了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
#include<string>
#include<fstream>
using namespace std;
#define rep(i, a, n) for(int i = a; i <= n; ++ i)
#define per(i, a, n) for(int i = n; i >= a; -- i)
typedef long long ll;
const int N = 5e6 + 105;
const int mod = 998244353;
const double Pi = acos(- 1.0);
const int INF = 0x3f3f3f3f;
const int G = 3, Gi = 332748118;
ll qpow(ll a, ll b) { ll res = 1; while(b){ if(b & 1) res = (res * a) % mod; a = (a * a) % mod; b >>= 1;} return res; }
ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
//
int n;
ll a[N];
int head[N], cnt = 0;
struct node{
int to, nxt, c;
}edge[N];
void add(int u, int v, int w){
edge[cnt].to = v, edge[cnt].c = w, edge[cnt].nxt = head[u], head[u] = cnt ++;
edge[cnt].to = u, edge[cnt].c = w, edge[cnt].nxt = head[v], head[v] = cnt ++;
}
struct XorTrie{
int cnt;
int t[N][2];
int L[N], R[N];
void _init(){
cnt = 0;
}
void Insert(ll x, int id){
int rt = 0;
for(int i = 32; i >= 0; -- i){
int op = x >> i & 1ll;
if(!t[rt][op]) t[rt][op] = ++ cnt;
rt = t[rt][op];
if(!L[rt]) L[rt] = id;
R[rt] = id;
}
}
ll ask(int rt, int pos, ll x){
ll res = 0;
for(int i = pos; i >= 0; -- i){
int op = x >> i & 1ll;
if(t[rt][op]) rt = t[rt][op];
else {
rt = t[rt][!op];
res += (1ll << i);
}
}
return res;
}
ll query(int rt, int pos){
if(t[rt][0] && t[rt][1]){
int x = t[rt][0], y = t[rt][1];
ll minn = 1e18;
for(int i = L[x]; i <= R[x]; ++ i)
minn = min(minn, ask(y, pos - 1, a[i]) + (1ll << pos));
return minn + query(t[rt][0], pos - 1) + query(t[rt][1], pos - 1);
}
else if(t[rt][0]) return query(t[rt][0], pos - 1);
else if(t[rt][1]) return query(t[rt][1], pos - 1);
return 0;
}
}trie;
void dfs(int u, int pre){
for(int i = head[u] ; i != -1; i = edge[i].nxt){
int v = edge[i].to, w = edge[i].c;
if(v == pre) continue;
a[v] = a[u] ^ w;
dfs(v, u);
}
}
int main()
{
memset(head, -1, sizeof(head));
trie._init();
scanf("%d",&n);
for(int i = 1; i < n; ++ i){
int x, y, z; scanf("%d%d%d",&x,&y,&z);
x ++; y ++;
add(x, y, z);
}
a[1] = 0;
dfs(1, -1);
sort(a + 1, a + n + 1);
for(int i = 1; i <= n; ++ i) trie.Insert(a[i], i);
printf("%lld
",trie.query(0, 32));
return 0;
}