【HDU-6191】Query on A Tree【Trie + DFS】

【HDU-6191】Query on A Tree【Trie + DFS】

问题链接:https://vjudge.net/problem/HDU-6191

Solution:

题目给了10s限时,一般这种时间的题目。。。所以直接暴力DFS或BFS就不用想了,如DFS复杂度O(nq),一般情况下都是会超时的,这题也不例外。解决办法是,DFS序,再根据每个结点二进制的数值维护字典树,我们其实是在构建一个字典树的森林。开一个idx数组,把每个结点原来的标号映射到DFS遍历的顺序上去,比如下面这棵树:

【注:[]内表示该结点的标号,:后面则是该结点的值】

通过DFS,建立起的idx数组将是下面这样:

为了看得清楚,将其映射后的编号标在树上是:

这样的顺序能够保证所有结点都出现在其父结点之后,开一个sz数组来存储下按照当前顺序每个结点之后多少个结点属于它就好了。

接着维护字典树,将每个结点的值转换为其二进制表示,则这棵字典树就是根据其值每个二进制位上0或1来建立的,按照上边的dfs序依次建立字典树,对于每个结点要建立字典树时,先继承(暂时想不到更合适的词)其dfs序前一个结点的对字典树中下一个结点的指向,之后根据当前二进制位上0或1创建新的字典树上结点(这里描述有些混乱,可以配合着阅读代码),用root来存储对于每个结点其在字典树数组中的根结点位置,查询的时候就根据输入的x值每个二进制位来查询,如果该位不存在于u结点及其子结点的字典树中,则结果的该位上就是0,反之就是1。下面的AC代码中使用role数组来标识每个trie树中的结点是由哪个dfs序标号的原来的结点创建的,也就是时间戳。对于query中的res,如果字典树中存在某个位置上相反的数,则最后异或出来的结果这位上便是1,反之只能是0,这样找出来的res必然使最大的。

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;

const int SIZE = 29;
const int LIM = 1e5 + 10;
const int NIL = -1;
int role[LIM * (SIZE + 3)], trie[LIM * (SIZE + 3)][2], root[LIM], values[LIM], sz[LIM];
int trie_size, node_size;
int idx[LIM];
vector<int> adj[LIM];

inline void init(int n) {
    trie_size = node_size = 0;
    memset(trie, 0, sizeof trie);
    memset(role, 0, sizeof role);
    memset(sz, 0, sizeof sz);
    for (int i = 1; i <= n; i++)
        adj[i].clear();
}

void update(int &crt, int pre, int vpos, int d) {
    crt = ++trie_size;
    trie[crt][0] = trie[pre][0];
    trie[crt][1] = trie[pre][1];
    role[crt] = role[pre] + 1;
    if (d == NIL) return;
    int key = (values[vpos] >> d) & 1;
    if (key) update(trie[crt][1], trie[pre][1], vpos, d - 1);
    else update(trie[crt][0], trie[pre][0], vpos, d - 1);
}

void dfs(int crt) {
    idx[crt] = ++node_size;
    sz[crt] = 1;
    update(root[idx[crt]], root[idx[crt] - 1], crt, SIZE);
    for (int i = 0; i < adj[crt].size(); i++) {
         dfs(adj[crt][i]);
         sz[crt] += sz[adj[crt][i]];
     }
}

int query(int lb, int rb, int x, int d, int res) {
    if (d == NIL) return res;
    int key = ((x >> d) & 1) ^ 1;
    int isInRange = role[trie[rb][key]] - role[trie[lb][key]];
    if (isInRange) return query(trie[lb][key], trie[rb][key], x, d - 1, res | (1 << d));
    else return query(trie[lb][key ^ 1], trie[rb][key ^ 1], x, d - 1, res);
}

int main(void) {
    int n, q;
    while (~scanf("%d%d", &n, &q)) {
        init(n);
        for (int i = 1; i <= n; i++)
            scanf("%d", values + i);
        for (int i = 2; i <= n; i++) {
            int p;
            scanf("%d", &p);
            adj[p].push_back(i);
        }
        dfs(1);
        int u, x;
        while (q--) {
            scanf("%d%d", &u, &x);
            printf("%d\n", query(root[idx[u] - 1], root[idx[u] + sz[u] - 1], x,  SIZE, 0));
        }
    }
}

 

注:编写时有参考了一些大神的博客,感谢大神分享,下面附上参考的博文链接:

https://www.cnblogs.com/Blackops/p/7493464.html

https://www.cnblogs.com/teble/p/8952322.html

https://blog.csdn.net/jinglinxiao/article/details/77803383