# Pishty and Tree

## 题目描述

A little boy Pishty lives in Khust – an ancient town in Uzhlyandia with their medieval castles and smart bears.
The gem of Khust is a very valuable castle because it protects the citizens of Uhzlyandia from the Durdom kingdom’s army. Pishty also like this castle because it hides old secrets in long halls and high towers…
The castle can be described as an undirected tree with $N$ vertices and $N-1$ edges. Each edge has a magic number $C$.
When a group of tourists visit the castle, they are interested in a path between vertices $U$ and $V$. They think that an edge is interesting if its magic number is less than or equal to $K$. The total attractivity of the path is the xor of all interesting edges on it.
The emperor of Uzhlyandia is interested in tourism development, and so he wants to find the total attractivity of the paths for each group. Because Pishty wants to become the emperor’s knight, he wants to know all of this information too. But he can’t do it on his own because there are a large number of groups. Please help Pishty to solve this unthinkable problem.
Given $M$ groups of tourists, find the total attractivity of the path for each group.

## 代码1

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
struct edge {
long long u, v, c, nxt;
bool operator < (const edge &a) const { return c < a.c; }
} e[200001], r[100001];
long long u, v, k, id, ans;
bool operator < (const ask &a) const { return k < a.k; }
} a[100001];
struct binary_indexed_tree {
long long n;
vector<long long> a;
void init(long long t) { n = t + 10, a.clear(), a.resize(n); }
void add(long long p, long long t) {
for (long long i = p; i < n; i += i & -i) a[i] ^= t;
}
long long sum(long long p) {
long long ret = 0;
for (long long i = p; i; i -= i & -i) ret ^= a[i];
return ret;
}
} tree[100001];
long long T, n, m, nume, tot, pnt, h[100001], size[100001];
long long up[100001], down[100001], father[100001], dist[100001];
long long id[100001], len[100001], cnt[100001];
void add_edge(long long u, long long v, long long c) {
e[++nume].u = u, e[nume].v = v, e[nume].c = c;
e[nume].nxt = h[u], h[u] = nume;
e[++nume].u = v, e[nume].v = u, e[nume].c = c;
e[nume].nxt = h[v], h[v] = nume;
}
void dfs(long long t, long long fa, long long depth) {
long long ma = 0;
size[t] = 1, father[t] = fa, dist[t] = depth;
for (long long i = h[t]; i; i = e[i].nxt) {
if (e[i].v != fa) {
dfs(e[i].v, t, e[i].c);
ma = max(ma, size[e[i].v]);
size[t] += size[e[i].v];
}
}
for (long long i = h[t]; i; i = e[i].nxt) {
if (e[i].v != fa && ma == size[e[i].v]) { down[t] = e[i].v; break; }
}
}
void init(long long t, long long fa, long long rt) {
if (!up[t]) id[up[t] = t] = ++tot, ++cnt[t], len[t] = 1;
else ++cnt[up[t] = rt], len[t] = len[fa] + 1;
for (long long i = h[t]; i; i = e[i].nxt) {
if (e[i].v != fa) {
if (!up[e[i].v]) init(e[i].v, t, e[i].v);
else init(e[i].v, t, rt);
}
}
if (t == up[t]) tree[id[t]].init(cnt[t]);
}
void insert_line(edge e) {
if (up[e.u] == up[e.v] && len[e.u] < len[e.v]) {
}
}
long long query(long long u, long long k) {
long long ret = 0;
while (u != 1) {
ret ^= tree[id[up[u]]].sum(len[u] - 1);
u = up[u];
if (u != 1) {
if (dist[u] <= k) ret ^= dist[u];
u = father[u];
}
}
return ret;
}
int main()
{
scanf("%lld", &T);
while (T--) {
scanf("%lld", &n);
nume = tot = 0, pnt = 1;
memset(h, 0, sizeof(h));
memset(up, 0, sizeof(up));
memset(down, 0, sizeof(down));
memset(cnt, 0, sizeof(cnt));
for (long long i = 1; i < n; ++i) {
r[i].nxt = 0;
scanf("%lld%lld%lld", &r[i].u, &r[i].v, &r[i].c);
}
sort(r + 1, r + n);
for (long long i = 1; i < n; ++i) add_edge(r[i].u, r[i].v, r[i].c);
dfs(1, 0, 0);
for (long long i = 1; i <= n; ++i) if (down[i]) up[down[i]] = i;
init(1, 0, 1);
scanf("%lld", &m);
for (long long i = 1; i <= m; ++i) {
a[i].id = i, a[i].ans = 0;
scanf("%lld%lld%lld", &a[i].u, &a[i].v, &a[i].k);
}
sort(a + 1, a + m + 1);
for (long long i = 1; i <= m; ++i) {
while (pnt <= nume && e[pnt].c <= a[i].k) insert_line(e[pnt++]);
a[i].ans = query(a[i].u, a[i].k) ^ query(a[i].v, a[i].k);
}
sort(a + 1, a + m + 1, cmp);
for (long long i = 1; i <= m; ++i) printf("%lld\n", a[i].ans);
}
return 0;
}


## 代码2

#include <cstdio>
#include <cstring>
using namespace std;
struct node_type {
long long val, child[2];
} node[4000001];
struct edge {
long long v, c, nxt;
} e[200001];
long long T, n, m, tot, nume, h[100001], root[100001];
void add_edge(long long u, long long v, long long c) {
e[++nume].v = v, e[nume].c = c, e[nume].nxt = h[u], h[u] = nume;
e[++nume].v = u, e[nume].c = c, e[nume].nxt = h[v], h[v] = nume;
}
long long insert_node(long long root, long long val, long long depth) {
if (depth < 0) {
node[++tot].val = node[root].val ^ val, node[tot].child[0] = node[tot].child[1] = 0;
}
long long t = (val >> depth) & 1;
long long ch = insert_node(node[root].child[t], val, depth - 1);
node[++tot].child[t] = ch, node[tot].child[!t] = node[root].child[!t];
node[tot].val = node[node[tot].child[t]].val ^ node[node[tot].child[!t]].val;
}
void dfs(long long t, long long fa) {
for (int i = h[t]; i; i = e[i].nxt) {
if (e[i].v != fa) {
root[e[i].v] = insert_node(root[t], e[i].c, 30);
dfs(e[i].v, t);
}
}
}
long long get_dist(long long root, long long k, long long depth) {
if (depth < 0) return node[root].val;
long long t = (k >> depth) & 1;
if (t) return node[node[root].child[0]].val ^ get_dist(node[root].child[1], k, depth - 1);
else return get_dist(node[root].child[0], k, depth - 1);
}
int main()
{
scanf("%lld", &T);
while (T--) {
scanf("%lld", &n);
nume = tot = 0;
memset(h, 0, sizeof(h));
for (int i = 1; i < n; ++i) {
long long u, v, c;
scanf("%lld%lld%lld", &u, &v, &c);
}
root[1] = insert_node(0, 0, 30);
dfs(1, 0);
scanf("%lld", &m);
for (int i = 1; i <= m; ++i) {
long long u, v, k;
scanf("%lld%lld%lld", &u, &v, &k);
printf("%lld\n", get_dist(root[u], k, 30) ^ get_dist(root[v], k, 30));
}
}
return 0;
}


418 I'm a teapot