HDU4757 Tree < LCA+可持久化Trie >

Problem

Tree

Description

Zero and One are good friends who always have fun with each other.
This time, they decide to do something on a tree which is a kind of graph that there is only one path from node to node. First, Zero will give One an tree and every node in this tree has a value. Then, Zero will ask One a series of queries. Each query contains three parameters: $x$, $y$, $z$ which mean that he want to know the maximum value produced by $z$ $xor$ each value on the path from node $x$ to node $y$ (include node $x$, node $y$). Unfortunately, One has no idea in this question. So he need you to solve it.

Input

There are several test cases and the cases end with $\mathrm{EOF}$. For each case:
The first line contains two integers $n(1\le n\le 10^5)$ and $m(1\le m\le 10^5)$, which are the amount of tree’s nodes and queries, respectively.
The second line contains $n$ integers $a[1..n]$ and $a[i]\;(0\le a[i]<2^{16})$ is the value on the $i^{th}$ node.
The next $n–1$ lines contains two integers $u$ $v$, which means there is an connection between $u$ and $v$.
The next m lines contains three integers $x$ $y$ $z$, which are the parameters of Zero’s query.

Output

For each query, output the answer.

Sample Input

3 2
1 2 2
1 2
2 3
1 3 1
2 3 2

Sample Output

3
0

Translation

给出一棵树，求两点$x,y$间树上链路中的数异或$z$得到的最大结果。

标签：LCA 可持久化Trie

Solution

最大异或和上树…
有异或，一个经典的解法就是建一棵$01$字典树，然后贪心跑一遍，尽量选和给出数当前位不同的数。
对于树上的此类问题，可以把Trie树可持久化，对于每个点，存它到根节点的路径上所有数的Trie树，这样是有前缀和性质的，求$\mathrm{LCA}$后作差即可求出链路上的数。
可持久化方法和主席树差不多。

Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#define MAX_N 100000
#define MAX_D 15
using namespace std;
int n, m, cnt, c[MAX_N+5], root[MAX_N+5];
int anc[MAX_N+5][MAX_D+5], dep[MAX_N+5];
bool vis[MAX_N+5];
vector <int> G[MAX_N+5];
struct node {int ls, rs, size;} trie[MAX_N*20+500];
void init() {
    root[0] = cnt = 0;
    memset(root, 0, sizeof(root));
    memset(anc, 0, sizeof(anc));
    memset(dep, 0, sizeof(dep));
    memset(vis, false, sizeof(vis));
    for (int i = 1; i <= n; i++)	G[i].clear();
}
void DFS(int u) {
    vis[u] = true;
    for (int i = 1; (1<<i) <= dep[u]; i++)	anc[u][i] = anc[anc[u][i-1]][i-1];
    for (int i = 0; i < G[u].size(); i++)
        if (!vis[G[u][i]])	anc[G[u][i]][0] = u, dep[G[u][i]] = dep[u]+1, DFS(G[u][i]);
}
int LCA(int a, int b) {
    int i, j;
    if (dep[a] < dep[b])	swap(a, b);
    for (i = 0; (1<<i) <= dep[a]; i++) ;	i--;
    for (j = i; j >= 0; j--)
        if (dep[a]-(1<<j) >= dep[b])
            a = anc[a][j];
    if (a == b)	return a;
    for (j = i; j >= 0; j--)
        if (anc[a][j] != anc[b][j])
            a = anc[a][j], b = anc[b][j];
    return anc[a][0];
}
void insert(int v, int o, int val, int range) {
    trie[v] = trie[o];
    if (range == 0) {trie[v].size++; return;}
    int x = val/range;
    if (x == 0)	insert(trie[v].ls = ++cnt, trie[o].ls, val%range, range/2);
    else	insert(trie[v].rs = ++cnt, trie[o].rs, val%range, range/2);
    trie[v].size = trie[trie[v].ls].size+trie[trie[v].rs].size;
}
void build(int u) {
    root[u] = ++cnt;
    insert(root[u], root[anc[u][0]], c[u], (1<<MAX_D));
    for (int i = 0; i < G[u].size(); i++)
        if (G[u][i] != anc[u][0])	build(G[u][i]);
}
int query(int v1, int v2, int v3, int v4, int x, int range) {
    if (range == 0)	return 0;
    int tmp1 = trie[trie[v1].ls].size+trie[trie[v2].ls].size-trie[trie[v3].ls].size-trie[trie[v4].ls].size;
    int tmp2 = trie[trie[v1].rs].size+trie[trie[v2].rs].size-trie[trie[v3].rs].size-trie[trie[v4].rs].size;
    if (x/range == 0) {
        if (tmp2)	return range+query(trie[v1].rs, trie[v2].rs, trie[v3].rs, trie[v4].rs, x%range, range/2);
        else	return query(trie[v1].ls, trie[v2].ls, trie[v3].ls, trie[v4].ls, x%range, range/2);
    } else {
        if (tmp1)	return range+query(trie[v1].ls, trie[v2].ls, trie[v3].ls, trie[v4].ls, x%range, range/2);
        else	return query(trie[v1].rs, trie[v2].rs, trie[v3].rs, trie[v4].rs, x%range, range/2);
    }
}
int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        init();
        for (int i = 1; i <= n; i++)	scanf("%d", &c[i]);
        for (int i = 1; i < n; i++) {int u, v; scanf("%d%d", &u, &v), G[u].push_back(v), G[v].push_back(u);}
        DFS(1);
        build(1);
        while (m--) {
            int u, v, x, lca;
            scanf("%d%d%d", &u, &v, &x);	lca = LCA(u, v);
            printf("%d\n", query(root[u], root[v], root[lca], root[anc[lca][0]], x, (1<<MAX_D)));
        }
        for (int i = 1; i <= cnt; i++)	trie[i].ls = trie[i].rs = trie[i].size = 0;
    }
    return 0;
}