## 【异或最小生成树】Graph – 20牛客多校5-B

### 传送门

#include<bits/stdc++.h>
using namespace std;
using namespace std;

const int N = 100010, M = 3000000;

int a[N], son[M][2], idx;

void insert(int x)
{
int p = 0;
for (int i = 30; i >= 0; i -- )
{
int &s = son[p][(x >> i) & 1];
if (!s) s = ++ idx;
p = s;
}
}

int search(int x)
{
int p = 0, res = 0;
for (int i = 30; i >= 0; i -- )
{
int s = (x >> i) & 1;
if (son[p][s])
p = son[p][s];
else res += 1 << i, p = son[p][!s];
}
return res;
}
int n;
long long ans;
void dfs(int l, int r, int dep)
{
if(dep == -1 || l >= r) return;
int mid = l - 1;
while(mid < r && ((a[mid + 1] >> dep) & 1) == 0) mid++;

dfs(l, mid, dep - 1); dfs(mid + 1, r, dep - 1);
if(mid == l - 1 || r == mid) return;
for(int i = l; i <= mid; i++) insert(a[i]);

int res = INT_MAX;
for(int j = mid + 1; j <= r; j++)
{
res = min(res, search(a[j]));
}
ans += res;
for(int j = 0; j <= idx; j++) son[j][0] = son[j][1] = 0;
idx = 0;
}

int e[N << 1], pre[N << 1], h[N], val[N << 1], cnt;
void add(int u, int v, int w)
{
e[cnt] = v; pre[cnt] = h[u]; val[cnt] = w; h[u] = cnt++;
}

int main()
{
cin.tie(0); cout.tie(0); ios::sync_with_stdio(0);
memset(h, -1, sizeof h);
cin >> n;
for(int i = 1; i < n; i++)
{
int u, v, w; cin >> u >> v >> w;
++u, ++v;
}
function<void(int,int,int) > fun = [&](int x, int fa, int v)
{
a[x] = v;
for(int i = h[x]; ~i; i = pre[i])
{
int y = e[i];
if(y == fa) continue;
fun(y, x, v ^ val[i]);
}
};
fun(1, - 1, 0);
sort(a + 1, a + 1 + n);
// for(int i = 1; i <= n; i++) cerr << a[i] << ' '; cerr << endl;
// cerr << "yes" << endl;
dfs(1, n, 29);
cout << ans << endl;
}