字典树

题目链接

核心思路

题目是要我们找到两个点，使得这两个点的路径上的边权异或值最大。

首先我们先别管这个树是个什么样的结构，我们需要清楚的就是看可以做个什么样的转换，使得挖掘到我们想要的性质。

我们令LCA代表的是X和Y的公共祖先，Root代表的是整棵树的根节点，Sum(X,Y)表示的是X到Y路径上面的边权异或和。

于是我们可以做以下推导：

\(Sum(X,Y)\)

\(=Sum(X,LCA)xorSum(Y,LCA)\)

\(=Sum(X,LCA)xorSum(Y,LCA)xorSum(LCA,Root)xorSum(LCA,Root)\)

\(=Sum(X,LCA)xorSum(LCA,Root)xorSum(Y,LCA)xorSum(LCA,Root)\)

\(=Sum(X,Root)xorSum(Y,Root)\)

所以我们只需要求出来根节点到每一个节点的异或和，然后找出一对使其异或值最小。

这里我们可以通过dfs求出来，假设dist数组是我们求出来的。

接下来再怎么做呢，这个就转换到了我们熟悉的问题，也就是使其两个数的异或和最大。

我们可以把这些数都插入到异或字典树里面去，然后一个一个的找。

比如我们要找dist[3]与他匹配的最大异或和。

那么我们可以从高位到低位一位一位的找，如果这一位是1，那么我们就去0这个分枝。如果这一位是0，那么我们就去1这个分枝。

其实就和这个题目是一样的

所以我们需要多总结我们做过的一些模型，有时候直接套板子就好了。

// Problem: A. Make it Beautiful
// Contest: Codeforces - Educational Codeforces Round 141 (Rated for Div. 2)
// URL: https://codeforces.com/contest/1783/problem/0
// Memory Limit: 512 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e7 + 10;
int e[N], h[N], ne[N], idx, w[N];
int tr[N][2];
int cnt;
int dist[N];
int en[N];
void add(int a, int b, int c)
{
	w[idx] = c;
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;

}
//求dist数组
void dfs(int u, int fa)
{
	for (int i = h[u];~i;i = ne[i])
	{
		int j = e[i];
		int val = w[i];
		if (j == fa)
			continue;
		dist[j] = (val ^= dist[u]);//j的父节点就是u
		dfs(j, u);
	}
}
void insert(int x)
{
	int p = 0;
	for (int i = 31;i >= 0;i--)
	{
		int k = ((x >> i) & 1);
		if (!tr[p][k])
			tr[p][k] = ++idx;
		p = tr[p][k];
	}
	en[p] = 1;
}
int find(int num)
{
	int p = 0;
	int sum = 0;
	for (int i = 31;i >= 0;i--)
	{
		int k = ((num >> i) & 1);
		if (tr[p][k ^ 1])
		{
			sum += (1 << i);
			p = tr[p][k ^ 1];
		}
		else
			p = tr[p][k];
	}
	return sum;
}



int main()
{
	memset(h, -1, sizeof h);
	int n;
	cin >> n;
	for (int i = 1;i <= n - 1;i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		add(a, b, c);
		add(b, a, c);
	}
	dist[1] = 0;
	dfs(1, -1);
	int sum = 0;
	/*for(int i=1;i<=n;i++)
		cout<<dist[i]<<" ";
		cout<<endl;*/
/*	dist[1]=0;
	dist[2]=3;
	dist[3]=5;
	dist[4]=7;*/
	for (int i = 1;i <= n;i++)
		insert(dist[i]);
	for (int i = 1;i <= n;i++)
	{
		sum = max(sum, find(dist[i]));
	}
	cout << sum << endl;
	return 0;


}