HDUOJ 6191 Query on A Tree

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6191

题意:给定一颗以1为根的树,每个节点上有固定点权,若干询问,每次询问数xy为根的子树中节点异或的最大值。

思路:首先先考虑一个序列,如果每次查询x与序列中的数异或的最大值的话,很明显的思路就是建个01字典树然后把x扔进去查询,如果序列变成区间的话,就要动用可持久化字典树来进行区间查询,然后这里放到了树上且查询子树,所以我们直接DFS序把树转成线性区间就可以查询了。

#pragma comment(linker, "/STACK:102400000,102400000")
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define Key_Value ch[ch[root][1]][0]
#define DBN1(a)           cerr<<#a<<"="<<(a)<<"\n"
#define DBN2(a,b)         cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<"\n"
#define DBN3(a,b,c)       cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<"\n"
#define DBN4(a,b,c,d)     cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<"\n"
#define DBN5(a,b,c,d,e)   cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<"\n"
#define DBN6(a,b,c,d,e,f) cerr<<#a<<"="<<(a)<<", "<<#b<<"="<<(b)<<", "<<#c<<"="<<(c)<<", "<<#d<<"="<<(d)<<", "<<#e<<"="<<(e)<<", "<<#f<<"="<<(f)<<"\n"
#define clr(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
const int INF=0x3f3f3f3f;
const int P=1000000000;
const double PI=acos(-1.0);
template<typename T> inline T gcd(T&a,T&b){return b==0?a:gcd(b,a%b);}
template<typename T> inline T lcm(T&a,T&b){return a/gcd(a,b)*b;}
template<typename T>
inline T read(T&x){
    x=0;int _f=0;char ch=getchar();
    while(ch<'0'||ch>'9')_f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x=_f?-x:x;
}
int n,q,dfs_clock,cnt,root[maxn],bin[31],l[maxn],r[maxn],v[maxn];
vector<int>G[maxn];
struct trie{
	int cnt;
	int ch[maxn*32][2];
	ll sum[maxn*32];
	void init(){
             cnt=0;
             memset(ch,0,sizeof(ch));
             memset(sum,0,sizeof(sum));
	}
	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 f){
    l[u]=++dfs_clock;
    root[l[u]]=trie.insert(root[l[u]-1],v[u]);
    for (int i=0;i<(int)G[u].size();i++){
        int v=G[u][i];
        if (v==f) continue;
        dfs(v,u);
    }
    r[u]=dfs_clock;
}
int main(){
    bin[0]=1;for(int i=1;i<=30;i++)bin[i]=bin[i-1]<<1;
    while (~scanf("%d%d",&n,&q)){
        for (int i=1;i<=n;i++) read(v[i]),l[i]=r[i]=0,G[i].clear();
        memset(root,0,sizeof(root));
        trie.init();
        for (int i=2;i<=n;i++){
             int x;read(x);
             G[x].push_back(i);
             G[i].push_back(x);
        }
        dfs_clock=0;
        dfs(1,0);
        for(;q--;){
            int u,x;read(u),read(x);
            printf("%d\n",trie.query(root[l[u]-1],root[r[u]],x));
        }
    }
    return 0;
}

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注