## 题目描述

Teachers of one programming summer school decided to make a surprise for the students by giving them names in the style of the “Hobbit” movie. Each student must get a pseudonym maximally similar to his own name. The pseudonym must be a name of some character of the popular saga and now the teachers are busy matching pseudonyms to student names.
There are $n$ students in a summer school. Teachers chose exactly $n$ pseudonyms for them. Each student must get exactly one pseudonym corresponding to him. Let us determine the relevance of a pseudonym $b$ to a student with name $a$ as the length of the largest common prefix $a$ and $b$. We will represent such value as $LCP(a, b)$. Then we can determine the quality of matching of the pseudonyms to students as a sum of relevances of all pseudonyms to the corresponding students.
Find the matching between students and pseudonyms with the maximum quality.

## 代码

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>

int min(int a, int b) {
return a < b ? a : b;
}

static const int N = 800005;
int numn = 1, tot;
char s[N];
struct Trie {
int child[26];
std :: vector <int> rec[2];
} node[N];
std :: vector <std :: pair <int, int> > ans;

void insert(char s[], int id, int val) {
int len = strlen(s), root = 0;
for (int i = 0; i < len; ++ i) {
if (! node[root].child[s[i] - 'a']) node[root].child[s[i] - 'a'] = numn ++;
root = node[root].child[s[i] - 'a'];
}
node[root].rec[val].push_back(id);
}

void merge(std :: vector <int> &a, std :: vector <int> &b) {
if (a.size() < b.size()) swap(a, b);
a.insert(a.end(), b.begin(), b.end());
}

void dfs(int t, int dep) {
for (int i = 0; i < 26; ++ i)
if (node[t].child[i]) {
dfs(node[t].child[i], dep + 1);
merge(node[t].rec[0], node[node[t].child[i]].rec[0]);
merge(node[t].rec[1], node[node[t].child[i]].rec[1]);
}
while (! node[t].rec[0].empty() && ! node[t].rec[1].empty()) {
tot += dep;
ans.push_back(std :: make_pair(node[t].rec[0][node[t].rec[0].size() - 1], node[t].rec[1][node[t].rec[1].size() - 1]));
node[t].rec[0].pop_back(), node[t].rec[1].pop_back();
}
}

int main() {
int n; scanf("%d", &n);
for (int i = 0; i < n; ++ i) scanf(" %s", s), insert(s, i + 1, 0);
for (int i = 0; i < n; ++ i) scanf(" %s", s), insert(s, i + 1, 1);
dfs(0, 0);
printf("%d\n", tot);
for (int i = 0; i < n; ++ i) printf("%d %d\n", ans[i].first, ans[i].second);
return 0;
}


## 题目描述

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;
}


## 题目描述

As you might remember from the previous round, Vova is currently playing a strategic game known as Rage of Empires.
Vova managed to build a large army, but forgot about the main person in the army – the commander. So he tries to hire a commander, and he wants to choose the person who will be respected by warriors.
Each warrior is represented by his personality – an integer number $p_i$. Each commander has two characteristics — his personality $p_j$ and leadership $l_j$ (both are integer numbers). Warrior $i$ respects commander $j$ only if $p_i \oplus p_j \lt l_j$ ($x \oplus y$ is the bitwise excluding OR of $x$ and $y$).
Initially Vova’s army is empty. There are three different types of events that can happen with the army:

• 1 $p_i$ – one warrior with personality $p_i$ joins Vova’s army;
• 2 $p_i$ – one warrior with personality $p_i$ leaves Vova’s army;
• 3 $p_i$ $l_i$ – Vova tries to hire a commander with personality $p_i$ and leadership $l_i$.

For each event of the third type Vova wants to know how many warriors (counting only those who joined the army and haven’t left yet) respect the commander he tries to hire.

## 代码

#include <iostream>
using namespace std;
int q, o, p, l;
struct trie_tree {
int tot = 1;
struct node_type {
int sum, child[2];
} a[2000001];
void insert(int t) {
int r = 1; ++a[r].sum;
for (int i = 26; i >= 0; --i) {
if (!a[r].child[(t >> i) & 1]) a[r].child[(t >> i) & 1] = ++tot;
r = a[r].child[(t >> i) & 1], ++a[r].sum;
}
}
void remove(int t) {
int r = 1; --a[r].sum;
for (int i = 26; i >= 0; --i) {
r = a[r].child[(t >> i) & 1], --a[r].sum;
}
}
int find(int p, int l) {
int r = 1, ret = 0;
for (int i = 26; i >= 0; --i) {
int s = (p >> i) & 1, t = (l >> i) & 1;
if (t && a[r].child[s]) ret += a[a[r].child[s]].sum;
if (t && a[r].child[!s]) r = a[r].child[!s];
else if (!t && a[r].child[s]) r = a[r].child[s];
else break;
}
return ret;
}
} tree;
int main()
{
cin >> q;
while (q--) {
cin >> o;
switch (o) {
case 1: {
cin >> p, tree.insert(p);
break;
}
case 2: {
cin >> p, tree.remove(p);
break;
}
default: {
cin >> p >> l;
cout << tree.find(p, l) << endl;
}
}
}
return 0;
}