做题集——(字典树+启发式合并+dfs)Query on A Tree

2 2
1 2
1
1 3
2 1

2
3

#include <bits/stdc++.h>
#define ll long long
using namespace std;
//dfs所有节点, 得到每一个节点下如果包含问题的异或最大值, 使用u表示同一个节点
//
const int MAXN = 1e5 + 7;
vector<int> E[MAXN];
int val[MAXN], ans[MAXN];
vector<pair<int, int> > ver[MAXN];
//用于建立字典树, 由于编号是乱序的, 所以可以全局共用
int nxt[MAXN * 32][2];
int Unuse[MAXN * 32], cnt, tot;
void Init(int n) {
    for (int i = 1; i <= n; i++) {
        E[i].clear();
        ver[i].clear();
    }
    cnt = tot = 0;
}
struct Trie {
    int root;
    int NewNode() {
        int rear;
        if (cnt) rear = Unuse[cnt--];
        else rear = ++tot;
        memset(nxt[rear], 0, sizeof(nxt[rear]));    //因为回收的节点其"指针"没有清除, 要除掉
        return rear;
    }
    void Init() {
        root = NewNode();
    }
    void Rec(int u) {
        if (nxt[u][0]) Rec(nxt[u][0]);
        if (nxt[u][1]) Rec(nxt[u][1]);
        Unuse[++cnt] = u;
    }
    void Insert(int x) {
        int now = root, tmp;
        for (int i = 31; i >= 0; i--) {
            tmp = (x >> i) & 1;
            if (!nxt[now][tmp]) nxt[now][tmp] = NewNode();
            now = nxt[now][tmp];
        }
        //遍历完后, now指向最后一位的叶节点, 一般可以对其进行操作来着
    }
    int Ask(int x) {
        int now = root, ret = 0, tmp;
        for (int i = 31; i >= 0; i--) {
            tmp = (x >> i) & 1;
            if (!nxt[now][tmp ^ 1]) now = nxt[now][tmp];//如果不存在可以找的节点, now指向同值子节点
            else {
                now = nxt[now][tmp ^ 1];
                ret = ret | (1 << i);//用或运算更省时间
            }
        }
        return ret;
    }
}t[MAXN];
vector<int> son[MAXN];
void Merge(vector<int>& v1, vector<int>& v2, Trie& t1, Trie& t2) {  //合并字典树
    if(v2.size() > v1.size()) swap(v1, v2), swap(t1, t2);
    t2.Rec(t2.root);
    for (int i = 0; i < v2.size(); i++) {
        v1.push_back(v2[i]);
        t1.Insert(v2[i]);
    }
    v2.clear();
}
void DFS(int u) {
    son[u].clear(); son[u].push_back(val[u]);
    t[u].Init(); t[u].Insert(val[u]);
    for (int i = 0; i < E[u].size(); i++) {
        int v = E[u][i];
        DFS(v);
        Merge(son[u], son[v], t[u], t[v]);
    }
    //当前节点下的子树已经全部遍历完毕, 回溯以下答案
    for (int i = 0; i < ver[u].size(); i++) {
        ans[ver[u][i].second] = t[u].Ask(ver[u][i].first);
    }
}

int main() {
    int n, q, u, v, x;
    while(~scanf("%d%d", &n, &q)) {
        Init(n);                    //初始化
        for (int i = 1; i <= n; i++) scanf("%d", &val[i]);
        for (int i = 2; i <= n; i++) {          
            scanf("%d", &v);
            E[v].push_back(i);             //将子节点存储进去
        }
        for (int i = 1; i <= q; i++) {          //读入u, x
            scanf("%d%d", &u, &x);
            ver[u].push_back(pair<int, int> (x, i));   //怎么理解这一步
        }
        DFS(1);
        for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
    }
    return 0;
}

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
#define mp make_pair
#define rep(i,l,r) for(int i=(l);i<=(r);++i)
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 2e5+5;;
const int M = 17;
const int mod = 1e9+7;
const int mo=123;
const double pi= acos(-1.0);
typedef pair<int,int>pii;
 
int bin[31];
int n,m,tot;
int a[N],root[N],id[N],st[N],ed[N];
vector<int>edg[N];
struct trie{
    int cnt;
    int ch[N*32][2],sum[N*32];
    void init(){
        met(ch,0);met(sum,0);
        cnt=0;
    }
    int insert(int x,int val){
        int tmp,y;tmp=y=++cnt;
        for(int i=30;i>=0;i--)
        {
            ch[y][0]=ch[x][0];ch[y][1]=ch[x][1];
            sum[y]=sum[x]+1;
            int t=val&bin[i];t>>=i;
            x=ch[x][t];
            ch[y][t]=++cnt;
            y=ch[y][t];
        }
        sum[y]=sum[x]+1;
        return tmp;
    }
    int query(int l,int r,int val){
        int tmp=0;
        for(int i=30;i>=0;i--)
        {
            int t=val&bin[i];t>>=i;
            if(sum[ch[r][t^1]]-sum[ch[l][t^1]])
                tmp+=bin[i],r=ch[r][t^1],l=ch[l][t^1];
            else r=ch[r][t],l=ch[l][t];
        }
        return tmp;
    }
}trie;
void dfs(int u,int fa){
    st[u]=++tot;
    id[tot]=u;
    for(int i=0;i<edg[u].size();i++){
        int v=edg[u][i];
        if(v==fa)continue;
        dfs(v,u);
    }
    ed[u]=tot;
}
int main(){
    bin[0]=1;for(int i=1;i<=30;i++)bin[i]=bin[i-1]<<1;
    while(~scanf("%d%d",&n,&m)){
        root[0]=0;tot=0;
        trie.init();
        for(int i=1;i<=n;i++)scanf("%d",&a[i]),edg[i].clear();
        for(int i=2;i<=n;i++){
            int v;
            scanf("%d",&v);
            edg[v].pb(i);
        }
        dfs(1,0);
        for(int i=1;i<=n;i++)root[i]=trie.insert(root[i-1],a[id[i]]);
        int l,r,x,u;
        while(m--){
            scanf("%d%d",&u,&x);
            l=st[u];r=ed[u];
            printf("%d\n",trie.query(root[l-1],root[r],x));
        }
    }
    return 0;
}