字典树_牛客博客

$Trie$

#include<iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
struct Trie{
    Trie *next[27];
    int num;
    Trie(){me(next,NULL);num=1;}
};
void insert(char *str,int n,Trie* &root){
    if(str[n]=='\0')return;
    int key=str[n]-'a';
    if(root->next[key]==NULL){
        root->next[key]=new Trie();
        insert(str,n+1,root->next[key]);
    }else {
        (root->next[key]->num)++;
        insert(str,n+1,root->next[key]);
    }
}
int query(char *str,Trie* root){
    Trie* p=root;
    int n=0;
    while(str[n++]){
        int key=str[n-1]-'a';
        if(p->next[key]==NULL)return 0;
        p=p->next[key];
    }
    return p->num;
}
void free_root(Trie* root){
    if(root==NULL)return;
    for(int i=0;i<26;i++)if(root->next[i])free_root(root->next[i]);
    delete(root);
}   
int main(){
    Trie *root=new Trie();
    char str[15];
    while(gets(str)&&str[0])insert(str,0,root);
    while(~scanf("%s",str))printf("%d\n",query(str,root));
    free_root(root);
}
or
#include<iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define me(a,x) memset(a,x,sizeof(a))
int Trie[1000005][26]={0};
int num[1000005]={0};
int tot=0;
void insert(char *str){
    int next=0,n=0;
    while(str[n++]){
        int key=str[n-1]-'a';
        if(Trie[next][key]==0)
        Trie[next][key]=++tot;
        num[Trie[next][key]]++;
        next=Trie[next][key];
    }
}
int query(char *str){
    int n=0,next=0;
    while(str[n++]){
        int key=str[n-1]-'a';
        if(Trie[next][key]==0)return 0;
        next=Trie[next][key];
    }return num[next];
}
int main(){
    char str[15];
    while(gets(str)&&str[0])insert(str);
    while(~scanf("%s",str))printf("%d\n",query(str));
}

$01Trie$

#include<iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
#define me(a,x) memset(a,x,sizeof(a))
struct Trie{
    int val;
    Trie *next[2];
    Trie(){
        val=-1;
        next[0]=next[1]=NULL;
    }
};
void insert(Trie* &root,int x,int bit){
    if(bit==-1){root->val=x;return;}
    int key=(1ll*x>>bit)&1;
    if(root->next[key]==NULL)root->next[key]=new Trie();
    insert(root->next[key],x,bit-1);
}
int query(Trie* root,int x,int bit){
    if(bit==-1)return root->val;
    int key=(1ll*x>>bit)&1;
    if(root->next[key^1]!=NULL)return query(root->next[key^1],x,bit-1);
    else return query(root->next[key],x,bit-1);
}
int main(){
    int t;cin>>t;
    for(int cas=1;cas<=t;cas++){
        int n,m;
        scanf("%d%d",&n,&m);
        Trie *root=new Trie();
        for(int i=0;i<n;i++){
            int u;scanf("%d",&u);
            insert(root,u,32);
        }
        printf("Case #%d:\n",cas);
        while(m--){
         int u;scanf("%d",&u);
         printf("%d\n",query(root,u,32));
        }
    }
}
or
#include<bits/stdc++.h>
using namespace std;
const int N=1e5;    
int Trie[N][2]={0};
int num[N];
int tot=0;
template<typename T>
struct Tree{
    void insert(T x){
        int next=0;
        for(int i=32;~i;i--){
            int key=(1ll*x>>i)&1;
            if(Trie[next][key]==0)Trie[next][key]=++tot;
            next=Trie[next][key];
        }
        num[next]=x;
    }
    T query(T x){
        int next=0;
        for(int i=32;~i;i--){
            int key=(1ll*x>>i)&1;
            if(Trie[next][key^1])next=Trie[next][key^1];
            else next=Trie[next][key];
        }
        return num[next];
    }
};

$可持久化01Trie$
Query on A Tree

#include<bits/stdc++.h>
#define me(a,x) memset(a,x,sizeof(a))
#define scnaf scanf 
#define itn int
using namespace std;
const int o_o=1e5+5;
const int mod=1e9+7;
const int oo=0x7fffffff;
const int sup=0x80000000;
typedef long long ll;
typedef unsigned long long ull;
int n,m,cnt=0,tot=0;
int Trie[o_o*40][2];
int st[o_o],ed[o_o],node[o_o];
int num[o_o*40],root[o_o*40];
int T[o_o*40];
vector<int>g[o_o];
void insert(int u,int fa,int val){
    int flag=0;
    for(int i=30;~i;i--){
        int key=val>>i&1;
        Trie[u][key]=++tot;
        if(!flag&&Trie[fa][key^1])Trie[u][key^1]=Trie[fa][key^1];
        if(flag){
            num[Trie[u][key]]++;
            u=Trie[u][key];
        }else{
            if(Trie[fa][key]){
                num[Trie[u][key]]=num[Trie[fa][key]]+1;
                u=Trie[u][key],fa=Trie[fa][key];
            }else{
                flag=1;
                num[Trie[u][key]]++;
                u=Trie[u][key];
            }
        }
    }
    root[u]=val;
}
int Q(int L,int R,int x){
    int flag=0;
    for(int i=30;~i;--i){
        int key=x>>i&1;
        if(flag){
            if(Trie[R][key^1])R=Trie[R][key^1];
            else R=Trie[R][key];
        }else{   
            if(Trie[R][key^1]){
                if(Trie[L][key^1]){
                    int cal=num[Trie[R][key^1]]-num[Trie[L][key^1]];
                    if(cal>0)R=Trie[R][key^1],L=Trie[L][key^1];
                    else R=Trie[R][key],L=Trie[L][key];
                }
                else{
                    R=Trie[R][key^1];
                    flag=1;
                }
            }else{
                R=Trie[R][key];
                if(Trie[L][key])L=Trie[L][key];else flag=1;
            }
        }
    }
    return x^root[R];
}
void dfs(int u){
    st[u]=++cnt;
    T[cnt]=++tot;
    insert(T[cnt],T[cnt-1],node[u]);
    for(auto v:g[u])dfs(v);
    ed[u]=cnt;
}
int main(){
    while(~scanf("%d%d",&n,&m)){
        me(Trie,0);
        cnt=tot=T[0]=num[0]=0;
        for(int i=1;i<=n;i++){
            g[i].clear();
            num[i]=0;
            root[i]=0;
            T[i]=0,st[i]=0,ed[i]=0;
            scnaf("%d",node+i);
        }
        for(int i=1;i<n;i++){
            int u;
            scnaf("%d",&u);
            g[u].push_back(i+1);
        }
        dfs(1);
        for(int i=1;i<=m;i++){
            int u,x;
            scnaf("%d%d",&u,&x);
            printf("%d\n",Q(T[st[u]-1],T[ed[u]],x));
        }
    }
}