hdu2846（动态字典树||静态字典树 模板）Repository

### 蓝桥杯竞赛中的最大异或结点问题 对于蓝桥杯竞赛中涉及的最大异或结点问题，通常涉及到二叉树结构以及按位运算特性。这类题目往往要求找到给定路径上节点值通过异或操作所能得到的最大结果。 #### 问题描述 假设存在一棵由若干个非负整数构成的完全二叉树，根节点编号为0，左子节点编号为2*i+1，右子节点编号为2*i+2（其中i表示当前节点）。目标是从任意起点出发到达叶子节点的过程中计算出所有经过节点数值相加后的总和，并求解这些可能路径之中两两之间进行异或运算所获得的最大值。 #### 算法设计 为了高效解决上述挑战，可以采用字典树(Trie)来存储每条从根到叶的不同前缀和。具体做法如下： - 初始化一个Trie数据结构用于保存遍历过程中遇到过的每一个前缀和； - 对于每次访问新节点时更新当前位置对应的累计和sum； - 利用已有的Trie查找最接近但又尽可能不同的另一个前缀和preSum'，使得两者之间的XOR差值最大化； ```cpp struct TrieNode { bool end; unordered_map<int, TrieNode*> children; TrieNode():end(false){} }; class Solution { public: void insert(TrieNode* root, int num){ for (int i = 31; ~i; --i){ // 插入num至trie中 int bit = ((num >> i) & 1); if (!root->children.count(bit)) root->children[bit] = new TrieNode(); root = root->children[bit]; } root->end = true; } int maxXorPair(TrieNode* root, int num){ int res = 0; for (int i = 31; ~i; --i){ int curBit = !((num>>i)&1); // 寻找相反位以获取更大xor值 if(root->children.find(curBit)!=root->children.end()) res |= (curBit << i), root=root->children[curBit]; else root=root->children[((num>>i)&1)]; } return res ^ num; } int solve(vector<vector<int>>& edges, vector<int>& values){ const int N=values.size(), M=(N<<1)-1; vector<int> adj[M], val(M); function<void(int,int)> dfs=[&](auto&& self, int u, int fa)->void{ static int idx=N-1; val[idx]=values[u]; for(auto v : adj[u]){ if(v==fa) continue; ++idx; adj[idx].push_back(u); adj[u].push_back(idx); self(self,v,u); } }; for(const auto& e:edges) adj[e[0]].emplace_back(e[1]),adj[e[1]].emplace_back(e[0]); dfs(dfs,0,-1); long long ans=INT_MIN; TrieNode *root=new TrieNode(); function<void(int,int,long long)> f=[&](auto &&self, int u, int p, long long sum)->void{ sum+=val[u]; ans=max(ans,maxXorPair(root,sum)); insert(root,sum); for(auto v:adj[u]) if(v!=p) self(self,v,u,sum); sum-=val[u]; // backtrack }; f(f,N-1,-1,0L); delete root; return ans; } }; ``` 此代码片段实现了基于DFS深度优先搜索构建完整二叉树并利用Trie记录各分支路径上的累积权重，在回溯过程中动态维护全局最优解的过程[^5]。