HDU – 6191 Query on A Tree 可持久化字典树+dfs序

Query on A Tree

可持久化字典树+dfs序

Source

HDU - 6191

2017ACM/ICPC广西邀请赛-重现赛（感谢广西大学）

My Solution

题意：给出一颗树，每个节点有一个权值，q个询问，询问以点u为根的子树中的节点权值异或x所得的值的最大值。

可持久化字典树+dfs序

对子树进行询问很容易想到dfs序，然后变成了线性的询问区间[l，r]内异或x所得的最大值，这个是可以用可持久化字典树来做，类似于主席树，每颗字典树维护的是区间[1,i]的信息，询问的时候，如果sum[r]-sum[l-1]大于0则说明在这个区间内这个值是存在的，然后按照通常的0-1树的做法，每次尽可能访问x&(1<<i)的异或值即可是答案尽可能大。

空间复杂度 O(nlogn)

时间复杂度 O(nlogn)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 8;

//可持久化字典树
int root[MAXN];
struct Persistent_Trie{
    int tot;
    int ch[32*MAXN][2], sum[32*MAXN]; //这里应该开logn+2倍
    void init(){
        tot = 0;
        memset(ch, 0, sizeof ch);
        memset(sum, 0, sizeof sum);
    }
    void _insert(int &rt, int last, int val){
        int state, i, t;
        rt = state = ++tot;
        for(i = 30; i >= 0; i--){
            ch[state][0] = ch[last][0];
            ch[state][1] = ch[last][1];
            sum[state] = sum[last] + 1;
            t = val & (1 << i); t >>= i;
            last = ch[last][t];
            ch[state][t] = ++tot;
            state = ch[state][t];
        }
        sum[state] = sum[last] + 1;
    }
    int query(int ss, int tt, int val){
        int res = 0, i;
        for(i = 30; i >= 0; i--){
            int t = val & (1 << i); t >>= i;
            if(sum[ch[tt][t^1]] - sum[ch[ss][t^1]]){
                res += (1 << i);
                tt = ch[tt][t^1];
                ss = ch[ss][t^1];
            }
            else tt = ch[tt][t], ss = ch[ss][t];
        }
        return res;
    }
} pt;

int a[MAXN];
//dfs序
vector sons[MAXN];
int p1[MAXN], p2[MAXN], ti = 0;
int dfsnum[MAXN];  //这个按情况是否需要。
inline void get_dfs_list(int u, int fa){
    p1[u] = ++ti;
    dfsnum[ti] = u; //
    int sz = sons[u].size(), i, v;
    for(i = 0; i < sz; i++){
        v = sons[u][i];
        if(v == fa) continue;
        get_dfs_list(v, u);
    }
    p2[u] = ti;
}



int main()
{
    //cout << (1<<30) << " " << (1 << 29) << endl;

    #ifdef LOCAL
    freopen("j.txt", "r", stdin);
    //freopen("j.out", "w", stdout);
    int T = 1;
    while(T--){
    #endif // LOCAL
    //ios::sync_with_stdio(false); cin.tie(0);

    int n, q, i, u, x;
    while(scanf("%d%d", &n, &q) != EOF){
        pt.init();
        for(i = 1; i <= n; i++){
            scanf("%d", &a[i]);
        }
        for(i = 1; i < n; i++){
            scanf("%d", &u);
            sons[u].push_back(i + 1);
        }
        ti = 0;
        get_dfs_list(1, 0);

        for(i = 1; i <= ti; i++){
            pt._insert(root[i], root[i-1], a[dfsnum[i]]);
        }
        while(q--){
            scanf("%d%d", &u, &x);
            printf("%dn", pt.query(root[p1[u]-1], root[p2[u]], x));
        }
        for(i = 1; i <= n; i++) sons[i].clear();

    }


    #ifdef LOCAL
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx