本文共 1655 字，大约阅读时间需要 5 分钟。
求树上的一条最长异或路径。
定义f(u, v)为u到v的路径， 那么显然f(1, u)^f(1, v) = f(u, v)， 想不到这个就没有办法做。
然后就可以用字典树查询+插入了。
用指针版本的狂T不止。
#include #include #include #include #include #include #include #include #include #include #include #include using namespace std;#define pb(x) push_back(x)#define ll long long#define mk(x, y) make_pair(x, y)#define lson l, m, rt<<1#define mem(a) memset(a, 0, sizeof(a))#define rson m+1, r, rt<<1|1#define mem1(a) memset(a, -1, sizeof(a))#define mem2(a) memset(a, 0x3f, sizeof(a))#define rep(i, n, a) for(int i = a; i pll;const double PI = acos(-1.0);const double eps = 1e-8;const int mod = 1e9+7;const int inf = 1061109567;const int dir[][2] = { {-1, 0}, { 1, 0}, { 0, -1}, { 0, 1} };const int maxn = 2e5+5;int head[maxn*2], num, val[maxn], top = 31, cnt;struct node{ int to, nextt, w;}e[maxn*2];void add(int u, int v, int w) { e[num].to = v, e[num].w = w, e[num].nextt = head[u], head[u] = num++;}void init() { num = cnt = 0; mem(val); mem1(head);}void dfs(int u, int fa) { for(int i = head[u]; ~i; i = e[i].nextt) { int v = e[i].to; if(v == fa) continue; val[v] = val[u]^e[i].w; dfs(v, u); }}struct Trie{ int next[2]; void init() { next[0] = next[1] = 0; }}trie[maxn];void insert(int pre) { int p = 0; for(int i = top-1; i>=0; i--) { int tmp = pre>>i&1; if(!trie[p].next[tmp]) { trie[p].next[tmp] = ++cnt; trie[cnt].init(); } p = trie[p].next[tmp]; }}int query(int pre) { int p = 0, ret = 0; for(int i = top-1; i>=0; i--) { int tmp = pre>>i&1; if(trie[p].next[tmp^1]) { ret |= 1<
转载于:https://www.cnblogs.com/yohaha/p/5084908.html