P4551 最长异或路径 : 01tire + 树 + 异或

题

P4551 最长异或路径 https://www.luogu.com.cn/problem/P4551

知识背景

01tire树，可以用来查找异或的最大值。
经典问题如下。在nums中，哪两个数中异或值最大。
解决方法：将nums 中的每个数，都塞进01tire树中。然后再每一个数从01tire树中找到最大的xor值
思路如图所示

01tire树模板如下

constexpr int DIGLEN = 31;
class Tire01Node {
public:
	Tire01Node* childs[2];
	int cnt;
	Tire01Node() {
		childs[0] = nullptr;
		childs[1] = nullptr;
		cnt = 0;
	}
	void insert(int num) {
		Tire01Node* p = this;
		for (int i = DIGLEN; i >= 0; i--) {
			int x = (num >> i) & 1;
			if(p->childs[x] == nullptr){
				p->childs[x] = new Tire01Node();
			}
			p = p->childs[x];
			p->cnt++;
		}
	}
	int findXorMax(int val) {
		Tire01Node* p = this;
		int ret = 0;
		for (int i = DIGLEN; i >= 0; i--) {
			int x = 1 ^ ((val >> i) & 1);
			if (p->childs[x] != nullptr && p->childs[x]->cnt > 0) {
				p = p->childs[x];
				ret |= (1 << i); 
			} else  p = p->childs[1^x];
			
		}
		return ret;
	}
};

code

此题ac代码如下

#define endl "\n"

constexpr int INF = 0x3f3f3f3f;
constexpr int NMAX = 100005;
using ll = long long;
using ull = unsigned long long;

using namespace std;

namespace Buffalo {
    constexpr int DIGLEN = 31;
	class Tire01Node {
	public:
	    Tire01Node* childs[2];
	    int cnt;
	    Tire01Node() {
	        childs[0] = nullptr;
	        childs[1] = nullptr;
	        cnt = 0;
	    }
	    void insert(int num) {
	        Tire01Node* p = this;
	        for (int i = DIGLEN; i >= 0; i--) {
	            int x = (num >> i) & 1;
	            if(p->childs[x] == nullptr){
	                p->childs[x] = new Tire01Node();
	            }
	            p = p->childs[x];
	            p->cnt++;
	        }
	    }
	    int findXorMax(int val) {
	        Tire01Node* p = this;
	        int ret = 0;
	        for (int i = DIGLEN; i >= 0; i--) {
	            int x = 1 ^ ((val >> i) & 1);
	            if (p->childs[x] != nullptr && p->childs[x]->cnt > 0) {
	                p = p->childs[x];
	                ret |= (1 << i); 
	            } else  p = p->childs[1^x];
	            
	        }
	        return ret;
	    }
	};
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N;
	cin >> N;
	vector<vector<pair<int, int>>> childs(N + 1);
	int u, v, w;
	vector<bool> isLeaf(N + 1);
	for (int i = 1; i < N; ++i) {
		cin >> u >> v >> w;
		isLeaf[v] = true;
		childs[u].emplace_back(v, w);
	}
	int root=1;
	for (; root <= N && isLeaf[root]; ++root);
	Buffalo::Tire01Node tire;
	vector<int> xorArr;
	function<void(int,int)> dfs = [&](int u,int val) {
		tire.insert(val);
		xorArr.emplace_back(val);
		for (auto& pairs : childs[u]) {
			dfs(pairs.first, pairs.second ^ val);
		}
	};
	dfs(root, 0);

	int ret = INT_MIN;
	for (auto& val : xorArr) {
		ret = max(ret, tire.findXorMax(val));
	}
	cout << ret << endl;
	return 0;
}