先求出dfs序，然后建立线段树，线段树每个节点套一个set。
修改操作只需要改被子树区间完全覆盖的线段树节点，将其节点中set的原来的值删除，加入新值。
询问操作查询单点到根的所有节点上的set中与查询值异或起来最大的那个。
查询set中的数与x异或的最大值，可以从高位到低位枚举二进制位，根据x的二进制位，查询一些set中数值的存在情况，例如加入x的二进制第y位为1，那么如果set中存在第y位为0的数字，明显可以使得答案更大。下面代码中这段的代码类似于二分。
时间复杂度O(nlogn^3)
代码
#include<cstdio>
#include<set>
#include<algorithm>
#include<cstring>
#define N 500010
using namespace std;
int n,m,i,a,b,typ;
int dp,p[N],pre[N],tt[N];
int tot,L[N],R[N],l[N],r[N],v[N],stack[N],deep,flag;
multiset<int> Set[N];
void link(int x,int y)
{
dp++;pre[dp]=p[x];p[x]=dp;tt[dp]=y;
}
void dfs()
{
int i;
while (deep)
{
if (L[stack[deep]]==)
{
tot++;
L[stack[deep]]=tot;
}
if (p[stack[deep]])
{
i=p[stack[deep]];
deep++;stack[deep]=tt[i];
p[stack[deep-]]=pre[i];
}
else
{
R[stack[deep]]=tot;
deep--;
}
}
}
void build(int x,int a,int b)
{
int m;
l[x]=a;r[x]=b;
Set[x].clear();
Set[x].insert(-);
Set[x].insert(<<);
if (b-a>)
{
m=(a+b)>>;
build(*x,a,m);
build(*x+,m,b);
}
}
void change(int x,int a,int b,int c,int d)
{
if ((a<=l[x])&&(r[x]<=b))
{
Set[x].insert(d);
if (flag)
Set[x].erase(c);
return;
}
int m=(l[x]+r[x])>>;
if (a<m) change(*x,a,b,c,d);
if (m<b) change(*x+,a,b,c,d);
}
int Q(int x,int y)
{
int l,r,m,p,q;
if (Set[x].size()==) return ;
l=;r=(<<)-;
while (l!=r)
{
m=(l+r)>>;
multiset<int>::iterator it=Set[x].upper_bound(m);
p=*it;
q=*(--it);
if (p>r)
r=m;
else
if (q<l)
l=m+;
else
{
if ((l^y)>((m+)^y))
r=m;
else
l=m+;
}
}
return l^y;
}
int query(int x,int a,int b,int c)
{
int ans=Q(x,c);
if ((a<=l[x])&&(r[x]<=b))
return ans;
int m=(l[x]+r[x])>>;
if (a<m) ans=max(ans,query(*x,a,b,c));
if (m<b) ans=max(ans,query(*x+,a,b,c));
return ans;
}
int main()
{
int test;
scanf("%d",&test);
while (test--)
{
scanf("%d%d",&n,&m);
dp=;
for (i=;i<=n;i++)
{
L[i]=;
p[i]=;
}
for (i=;i<=n;i++)
{
scanf("%d",&a);
link(a,i);
}
tot=;
deep=;stack[]=;
dfs(); build(,,n);
flag=;
for (i=;i<=n;i++)
{
scanf("%d",&v[i]);
change(,L[i]-,R[i],,v[i]);
}
flag=;
for (i=;i<=m;i++)
{
scanf("%d",&typ);
if (typ==)
{
scanf("%d%d",&a,&b);
change(,L[a]-,R[a],v[a],b);
v[a]=b;
}
else
{
scanf("%d",&a);
printf("%d\n",query(,L[a]-,L[a],v[a]));
}
}
}
}