题意：n个点的一棵树，树的边上有权值。一条路径的权值定义成这条路径上所有边的权值的xor。问所有路径的最大权值是多少。
思路：
首先，树上任意两点之间的路可以表示成 这两点到根节点的路- 其最近公共祖先到根节点的路*2.那么这里如果是用xor操作，重复的那部分正好就没了。
深搜一边，得出所有点到根节点的权值，这样问题就边成了n个数字，将其中两个xor，问得到的最大值是什么。
然后这里我卡住了……实际上做法非常……
用字典树记录所有这些树（二进制），然后对每一个数，去找现在存在的和它xor之后答案最大的那个数。暴力完n个数就得到答案= =……
坑：深度太深爆栈了。只能自己写。用栈模拟了递归，但感觉又不像是深搜又不像是广搜……兼有两个特点，姑且称为广深搜吧……
新品种：广深搜
实现方法：用栈代替队列实现广搜，就出现这奇特的品种。
优点：代替深搜防爆栈，代替广搜省内存。
缺点：用之前谨慎……看看问题是不是能用这种方法解决。
代码：
/* * 树上两点之间路径 = 两点到根的路径 - 最近公共祖先到根的路径*2 * 字典树，暴力每个数，找其配对的尽量大的数 * 坑点：dfs 深搜爆栈， 字典树节点要开到至少15倍……（估计最大32倍吧） */ #include <cstdio> #include <cstring> #define N 100010 struct Graph{ struct Edge{ int to, next, c; }e[N<<2]; int head[N]; int p; void init() { memset(head, -1, sizeof(head)); p = 0; } void add(int u, int v, int c) { e[p].to = v; e[p].c = c; e[p].next = head[u]; head[u] = p++; } }g; int dis[N]; struct Dictree{ struct Node { int val[2]; void init() { memset(val, -1, sizeof(val)); } }node[N<<4]; // 够么？ int p; void init() { node[0].init(); p = 1; } void insert(int x) { int now = 0; for (int i = 30; i >= 0; i--) { int k = ((x>>i)&1); if (node[now].val[k] == -1) { node[p].init(); node[now].val[k] = p++; } now = node[now].val[k]; } } int find(int x) { int now = 0; int ans = 0; for (int i = 30; i >= 0; i--) { int k = ((x>>i)&1); if (node[now].val[k] == -1) { k = !k; } ans = ((ans<<1)|k); now = node[now].val[k]; } return ans; } }dict; int stk[N]; void dfs(int now) { int top = 0; stk[top++] = now; while (top) { now = stk[--top]; dict.insert(dis[now]); for (int i = g.head[now]; i != -1; i = g.e[i].next) { int to = g.e[i].to; int c = g.e[i].c; if (dis[to] == -1) { dis[to] = dis[now]^c; stk[top++] = to; } } } } int main() { int n; while (scanf("%d", &n) != EOF ){ g.init(); for (int i = 0; i < n-1; i++) { int a, b, c; scanf("%d%d%d", &a, &b, &c); g.add(a,b,c); g.add(b,a,c); } memset(dis, -1, sizeof(dis)); //会不会^出-1? dis[1] = 0; dict.init(); dfs(1); int maxans = 0; for (int i = 1; i <= n; i++) { int ans = dis[i]^dict.find(~dis[i]); if (maxans < ans) maxans = ans; } printf("%d ", maxans); } return 0; }