laekov

The input contains several test cases.

虽然我没看到这句话但也A了，什么情况。

a到b的路径xor=(a到根xor b到根) 水

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

struct edge {

int t, v;

edge *next;

};

const int maxn = 100009;

const int maxl = 33;

int n, v[maxn], fa[maxn], tr[maxn * maxl][2], tn;

edge *head[maxn], *ep;

inline void addEdge(int u, int v, int w) {

ep-> t = v;

ep-> v = w;

ep-> next = head[u];

head[u] = ep ++;

}

void buildTree() {

static int q[maxn];

int hd = 0, tl = 1;

memset(fa, -1, sizeof(fa));

fa[1] = 0;

q[hd] = 1;

v[1] = 0;

while (hd < tl) {

int p = q[hd ++];

for (edge* e = head[p]; e; e = e-> next)

if (fa[e-> t] == -1) {

fa[e-> t] = p;

v[e-> t] = v[p] ^ e-> v;

q[tl ++] = e-> t;

}

}

}

void trieIns(int v) {

int p = 1;

for (int i = 30; i >= 0; -- i) {

int d = (v >> i) & 1;

if (!tr[p][d])

tr[p][d] = ++ tn;

p = tr[p][d];

}

}

int trieXor(int v) {

int p = 1, s = 0;

for (int i = 30; i >= 0; -- i) {

int d = (v >> i) & 1;

if (tr[p][d ^ 1]) {

s |= (1 << i);

p = tr[p][d ^ 1];

}

else

p = tr[p][d];

}

return s;

}

int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif

scanf("%d", &n);

memset(head, 0, sizeof(head));

ep = new edge[maxn * 2];

for (int i = 0; i < n - 1; ++ i) {

int u, v, w;

scanf("%d%d%d", &u, &v, &w);

addEdge(u, v, w);

addEdge(v, u, w);

}

buildTree();

tr[0][0] = 0;

tr[0][1] = 0;

tr[1][0] = 0;

tr[1][1] = 0;

tn = 2;

for (int i = 1; i <= n; ++ i)

trieIns(v[i]);

int ans = 0;

for (int i = 1; i <= n; ++ i)

ans = max(ans, trieXor(v[i]));

printf("%d\n", ans);

}