HDU 6191 && 2017广西邀请赛：Query on A Tree（字典树启发式合并）

题意：

有一棵n个节点的树，每个节点都有一个值，m次查询，每次两个数x y表示以x为根的子树中哪个节点权值异或y得出的结果最大，求最大结果

离线

和线段树合并一样，在搜索过程中将多个字典树并在一起

每次查询遍历以当前子树的根为根的字典树

01字典树：http://blog.csdn.net/jaihk662/article/details/53914904

#pragma comment(linker, "/STACK:102400000,102400000")
#include<stdio.h>
#include<vector>
#include<string.h>
#include<stdlib.h>
using namespace std;
typedef struct
{
	int x;
	int id;
}Res;
Res temp;
typedef struct Trie
{
	Trie *next[2];
}Trie;
vector<int> G[100001];
vector<Res> Q[100001];
int val[100001], ans[100001];
Trie *root[100001];
void Update(Trie *q, int a)
{
	int i, now;
	Trie *p = q;
	for(i=29;i>=0;i--)
	{
		now = 0;
		if(a&(1<<i))
			now = 1;
		if(p->next[now]==NULL)
		{
			Trie *temp = new Trie;
			temp->next[0] = temp->next[1] = NULL;
			p->next[now] = temp;
		}
		p = p->next[now];
	}
}
int Query(Trie *q, int a)
{
	int i, now, bet;
	bet = 0;
	Trie *p = q;
	for(i=29;i>=0;i--)
	{
		now = 0;
		if(a&(1<<i))
			now = 1;
		if(p->next[now^1]!=NULL)
		{
			p = p->next[now^1];
			bet |= (1<<i);
		}
		else
			p = p->next[now];
	}
	return bet;
}
Trie* Merge(Trie *p, Trie *q)
{
	if(p==NULL)
		return q;
	if(q==NULL)
		return p;
	p->next[0] = Merge(p->next[0], q->next[0]);
	p->next[1] = Merge(p->next[1], q->next[1]);
	free(q);
	return p;
}
void Delete(Trie *q)
{
	int i;
	if(q->next[0])
		Delete(q->next[0]);
	if(q->next[1])
		Delete(q->next[1]);
	free(q);
}
void Sech(int u)
{
	int i, v;
	root[u] = new Trie;
	root[u]->next[1] = root[u]->next[0] = NULL;
	Update(root[u], val[u]);
	for(i=0;i<G[u].size();i++)
	{
		v = G[u][i];
		Sech(v);
		root[u] = Merge(root[u], root[v]);
	}
	for(i=0;i<Q[u].size();i++)
		ans[Q[u][i].id] = Query(root[u], Q[u][i].x);
}
int main(void)
{
	int n, q, i, x, y;
	while(scanf("%d%d", &n, &q)!=EOF)
	{
		memset(ans, 0, sizeof(ans));
		for(i=1;i<=n;i++)
		{
			G[i].clear();
			Q[i].clear();
			scanf("%d", &val[i]);
		}
		for(i=2;i<=n;i++)
		{
			scanf("%d", &x);
			G[x].push_back(i);
		}
		for(i=1;i<=q;i++)
		{
			scanf("%d%d", &y, &x);
			temp.x = x, temp.id = i;
			Q[y].push_back(temp);
		}
		Sech(1);
		for(i=1;i<=q;i++)
			printf("%d\n", ans[i]);
		Delete(root[1]);
	}
}