tire树求最大最下异或和

题目描述

给定一棵 $n$ 个节点的二叉树，每个节点上有一个整数。求二叉树中某个子树内的最大和最小数的异或和。

输入格式

第一行包含整数 $n$。

以下 $n$ 行每行描述二叉树的一个节点，格式为 ID val lson rson，其中 ID 表示节点编号（范围 1∼n），val 是节点上的整数，lson 和 rson 分别表示该节点的左儿子和右儿子的编号。若节点没有左儿子或右儿子，则对应位置为 0。

输出格式

一个整数，表示异或和。

数据范围

1≤n≤10^5,−10^9≤val≤10^9

输入样例1：

5
1 1 2 3
2 2 4 5
3 3 0 0
4 4 0 0
5 5 0 0

输出样例1：

7

输入样例2：

9
1 1 2 3
2 2 4 5
3 3 6 7
4 4 8 9
5 5 0 0
6 6 0 0
7 7 0 0
8 8 0 0
9 9 0 0

输出样例2：

8

算法

(Trie 树,后缀数组,分块) $O(n log n + n \log^2 mod)$

C++ 代码

用Trie树实现

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<stdlib.h>
#include<time.h>
using namespace std;
#define f(a,b,c) for(a=b;a<=c;a++)
#define g(a,b,c) for(a=b;a>=c;a--)
#define ll long long
const ll INF=2e9;
const int N=1e5+7,M=1e6+7;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}

int e[M],ne[M],h[N],idx;
void add(int a,int b){e[idx]=b;ne[idx]=h[a];h[a]=idx++;}
int fa[N],dep[N],sz[N],son[N],wson[N],dfn[N],dnt,ndfn[N],tp[N];

struct Trie{
    int son[2],cnt;
}tr[N*32];
int rt[N];
int cnt;
void update(int u,int k){
    int p=rt[u],q=rt[cnt++];
    int i,j;
    rt[u]=q,tr[q]=tr[p];
    f(i,30,0){
        tr[q].cnt=tr[p].cnt+1;
        j=(k>>i)&1;
        if(tr[p].son[j]==0){
            tr[q].son[0]=tr[p].son[0],tr[q].son[1]=tr[p].son[1];
            tr[q].son[j]=cnt++,tr[tr[q].son[j]]=(Trie){0,0};
        }
        p=tr[p].son[j],q=tr[q].son[j];
    }
    tr[q].cnt=tr[p].cnt+1;
}
int query(int u,int v,int k){
    int p=rt[u],q=rt[v],res=0;
    int i,j;
    f(i,30,0){
        j=(k>>i)&1;
        if(tr[tr[q].son[j^1]].cnt>tr[tr[p].son[j^1]].cnt) res=res|(1<<i),q=tr[q].son[j^1],p=tr[p].son[j^1];
        else q=tr[q].son[j],p=tr[p].son[j];
    }
    return res;
}
void dfs1(int u,int la){
    dep[u]=dep[la]+1,fa[u]=la,sz[u]=1;
    int i,v,maxn=-1;
    for(i=h[u];~i;i=ne[i]){
        v=e[i];
        if(v==la) continue;
        dfs1(v,u);
        sz[u]+=sz[v];
        if(sz[v]>maxn) maxn=sz[v],son[u]=v;
    }
}
void dfs2(int u){
    int i,v;
    dfn[u]=++dnt,ndfn[dnt]=u;
    if(son[u]) wson[son[u]]=dfn[son[u]],tp[son[u]]=tp[u],dfs2(son[u]);
    else return;
    for(i=h[u];~i;i=ne[i]){
        v=e[i];
        if(v==fa[u]||v==son[u]) continue;
        wson[v]=dfn[v],tp[v]=v,dfs2(v);
    }
}

int find(int u,int v){
    int f1=tp[u],f2=tp[v];
    int ans=0;
    while(f1!=f2){
        if(dep[f1]<dep[f2]) swap(u,v),swap(f1,f2);
        ans=max(ans,query(wson[f1],wson[u],v));
        u=fa[f1],f1=tp[u];
    }
    if(u==v) return ans;
    if(dep[u]<dep[v]) swap(u,v);
    return max(ans,query(wson[son[v]],wson[u],v));
}
int main(){

    int n=read();
    memset(h,-1,sizeof h);
    int i,a,b,c,ans1=0x3f3f3f3f,ans2=-0x3f3f3f3f;
    f(i,1,n){
        a=read(),b=read(),c=read();
        if(c){
            add(a,c),add(c,a);
            add(b,c),add(c,b);
        }
        else{
            add(a,b),add(b,a);
        }
    }
    dfs1(1,0),wson[1]=dfn[1],tp[1]=1,dfs2(1);
    rt[0]=cnt++,tr[rt[0]]=(Trie){0,0};
    f(i,1,n){
        a=ndfn[i];
        rt[a]=rt[fa[a]];
        update(a,read());
    }
    f(i,1,n){
        a=ndfn[i];
        ans1=min(ans1,query(rt[1],rt[a],read()));
        ans2=max(ans2,query(rt[1],rt[a],read()));
    }
    cout<<ans1+ans2;
    return 0;
}

'''