EOJ 2021.10 E. XOR tree

E. XOR tree

Method 1 ： First open a big pile . then $dfs$ Again , Build a persistent dictionary tree , And each point throws the XOR maximum of itself and its ancestors into the heap . loop $k$ Time , Each time the maximum value is ejected from the heap , Suppose the ejected point has been ejected $x$ Time , Search the dictionary tree for its number $x+1$ Large XOR value , Then throw it into the pile . Time complexity $O(30n+k(logn+30))$

1. This problem also reflects a skill, that is, to do the first k Great value (k<$1e6$) The common method is to maintain a priority queue, get the maximum value each time, and then update .
2. The problem is no x All nodes can be persistent. The dictionary tree represents from the root to x The point group on the node chain Chengdu dictionary tree . Although in this way and query x The dictionary tree corresponding to the subtree of the node is equivalent , But in fact, this method can save one of tree chain partition when dealing with tree chain problem log

#include<bits/stdc++.h>
using namespace std;
struct
{
    
    int vis[2];
    int num;
}trie[30000005];
int tot;
int root[5000005];
int insert(int x,int rt)
{
    
    int Root=++tot;
    int now=root[rt];
    for(int i=30;i>=0;i--)
    /// This is determined according to the scope , The first one here is (1>>30) That is to say 2^31
    {
    
        int ch=(x>>i)&1;

        trie[tot]=trie[now];
        trie[tot].vis[ch]=tot+1;
        trie[tot].num++;

        now=trie[now].vis[ch];
        tot++;
    }
    trie[tot]=trie[now];
    trie[tot].num++;
    return Root;
    /// The reason for this is that it is convenient to build a tree root[x]=insert(a[x],i-1);
}
int query(int x,int k,int rt)
/// Inquire about x stay root[rt] The root of the persistent dictionary tree is XOR k Big 
{
    
    int now=root[rt];
    int ans=0;
    for(int i=30;i>=0;i--)
    {
    
        int ch=(x>>i)&1;
        if(trie[trie[now].vis[!ch]].num>=k)
        {
    
            now=trie[now].vis[!ch];
            ans|=(1<<i);
        }
        else
        {
    
            k-=trie[trie[now].vis[!ch]].num;
            now=trie[now].vis[ch];
        }
    }
    return ans;
}
struct node
{
    
    int val,id,now;
    bool operator < (const node &ths)const
    {
    
        if(val!=ths.val)return val<ths.val;
        if(now!=ths.now)return now<ths.now;
        return id<ths.id;
    }
};
int dep[1000005],fa[1000005],a[1000005];
vector<int>v[1000005];
priority_queue<node>q;
void dfs(int x,int pre)
{
    
    if(pre!=0)
    {
    
        dep[x]=dep[pre]+1;
        fa[x]=pre;
        q.push({
    query(a[x],1,fa[x]),x,1});
    }
    root[x]=insert(a[x],pre);
    for(auto to:v[x])if(to!=pre)
    {
    
        dfs(to,x);
    }
}
vector<int>ans;
int main()
{
    
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<n;i++)
    {
    
        int tu,tv;
        scanf("%d%d",&tu,&tv);
        v[tu].push_back(tv);
        v[tv].push_back(tu);
    }
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    dfs(1,0);

    for(int i=1;i<=k;i++)
    {
    
        node p=q.top();
        q.pop();
        ans.push_back(p.val);
        if(p.now<dep[p.id])q.push({
    query(a[p.id],p.now+1,fa[p.id]),p.id,p.now+1});
    }
    for(auto x:ans)printf("%d\n",x);
    return 0;
}

Method 2 ： First create a persistent dictionary tree , Then two points k Great value , Then traverse all the dictionary trees violently to get the answer .