[hdu 6191 Query on A Tree] 사전 트 리 시작 식 병합

[hdu 6191 Query on A Tree] 사전 트 리 시작 식 병합
분류: Data Structure Trie Tree1. 제목 링크
[hdu 6191 Query on A Tree]
2. 제목 설명
n 개의 노드 가 있 는 나 무 는 노드 마다 가중치 가 있 습 니 다.그 다음 에 q 개의 질문 은 매번 두 개의 수 u, x 를 포함 하고 u 를 루트 노드 로 하 는 서브 트 리 의 모든 노드 의 가중치 xor x 의 최대 치 를 조회 합 니 다.
3. 문제 풀이 사고방식
이 문 제 는 두 가지 사고방식 이 있다. 첫 번 째 방법 은 dfs 순서 + 지속 가능 한 사전 트 리 이다.두 번 째 방법 은 오프라인 모든 문의 입 니 다.그리고 트 리 를 뒷 차례 dfs 로 옮 겨 다 닐 때 시작 식 으로 사전 트 리 를 합 쳐 답 을 기록 합 니 다.
4. 구현 코드

#include 
using namespace std;

typedef long long ll;
typedef long double lb;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair pll;
typedef pair puu;
typedef pair pbb;
typedef vector<int> vi;

const int inf = 0x3f3f3f3f;
const ll infl = 0x3f3f3f3f3f3f3f3fLL;
template<typename T> inline void umax(T &a, T b) { a = max(a, b); }
template<typename T> inline void umin(T &a, T b) { a = min(a, b); }
template<typename T> inline T randIntv(const T& a, const T& b) { return (T)rand() % (b - a + 1) + a; }

const int MAXN = 100005;
struct Edge {
    int v, next;
} edge[MAXN];
int n, q, head[MAXN], tot;
ll w[MAXN];

void edge_init() {
    tot = 0;
    memset(head, -1, sizeof(head));
}
void edge_ins(int u, int v) {
    edge[tot] = Edge{v, head[u]};
    head[u] = tot ++;
}

struct Trie {
    static const int BITS = 40;
    static const int null = 0;
    struct TNode {
        int ch[2];
        void I() { ch[0] = ch[1] = 0; }
    } node[MAXN * 50];
    int root[MAXN], tot;
    void init() {
        node[tot = 0].I();
    }
    int new_node() {
        node[++ tot].I();
        return tot;
    }
    void ins(int u, const ll x) {
        int pos = root[u] = new_node();
        for (ll i = BITS - 1; i >= 0; --i) {
            ll j = (x >> i) & 1;
            if (node[pos].ch[j] == null) node[pos].ch[j] = new_node();
            pos = node[pos].ch[j];
        }
    }
    int merge(const int u, const int v) {
        if (u == null) return v;
        if (v == null) return u;
        node[u].ch[0] = merge(node[u].ch[0], node[v].ch[0]);
        node[u].ch[1] = merge(node[u].ch[1], node[v].ch[1]);
        return u;
    }
    ll query(const int u, const ll x) {
        ll ret = 0; int pos = root[u];
        for (ll i = BITS - 1; i >= 0; --i) {
            ll j = (x >> i) & 1;
            if (node[pos].ch[j ^ 1] != null) {
                pos = node[pos].ch[j ^ 1];
                ret = ret << 1ll | 1ll;
            } else {
                pos = node[pos].ch[j];
                ret = ret << 1ll;
            }
            assert(pos != null);
        }
        return ret;
    }
} trie;

vector qr[MAXN];
ll res[MAXN];

void dfs(int u, int fa) {
    trie.ins(u, w[u]);
    for (int i = head[u]; ~i; i = edge[i].next) {
        int v = edge[i].v;
        if (v == fa) continue;
        dfs(v, u);
        trie.merge(trie.root[u], trie.root[v]);
    }
    for (auto &e : qr[u]) {
        res[e.first] = trie.query(u, e.second);
    }
}

int main() {
#ifdef ___LOCAL_WONZY___
    freopen ("input.txt", "r", stdin);
#endif // ___LOCAL_WONZY___
    while (~scanf("%d %d", &n, &q)) {
        for (int i = 1; i <= n; ++i) {
            scanf("%lld", &w[i]);
        }
        edge_init();
        for (int i = 2; i <= n; ++i) {
            int fa; scanf("%d", &fa);
            edge_ins(fa, i);
        }
        trie.init();
        for (int i = 1; i <= q; ++i) {
            int u; ll x; scanf("%d %lld", &u, &x);
            qr[u].push_back(pll(i, x));
        }
        dfs(1, 1);
        for (int i = 1; i <= q; ++i) {
            printf("%lld
", res[i]);
        }
        for (int i = 1; i <= n; ++i) qr[i].clear();
    }
#ifdef ___LOCAL_WONZY___
    cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC * 1000 << " ms." << endl;
#endif // ___LOCAL_WONZY___
    return 0;
}