题目
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5709
给定一棵树，每个节点有颜色，每次询问给出\(x,d\)，要求输出在\(x\)的字数内，所有距离\(x\)不超过\(d\)的点的颜色总数。定义两点之间的距离为边数\(+1\)。
思路
调了\(6h\)才调处来。。。心态爆炸。
对于每一个节点开两棵线段树。
- \(x\)节点的第一棵线段树的区间\([l,r]\)表示在\(x\)的子树中，深度在\([l,r]\)之内的点有多少种第一次出现的颜色，也就是说，如果深度在\([dep[x],l-1]\)有颜色\(p\)，深度在\([l,r]\)中也有颜色\(p\)，那么颜色\(p\)对\([l,r]\)是不做贡献的，因为在\(x\)的字数内深度更浅处已经出现了颜色\(p\)。
- \(x\)节点的第二棵线段树只有叶子结点有用，叶子结点\([i,i]\)表示颜色\(i\)在\(x\)的子树内的最浅深度。
那么显然，对于一个询问\(x,d\)，其答案就是在\(x\)的第一棵线段树中查询区间\([dep[x],dep[x]+d]\)的和，因为我们保证了每种颜色只有深度最浅才有贡献，所以不用担心拆分成两个子区间时两个子区间的贡献有重复。
假设我们已经处理好了\(x\)的子树，那么现在需要维护\(x\)的两棵线段树。
首先对于第一棵线段树，我们先直接合并。这样会造成贡献重复。比如说\(x\)的两个子节点\(y_1,y_2\)，它们的子树中都含有颜色\(p\)，那么直接合并时，颜色\(p\)就会对\(x\)做两次贡献。
那么我们只需要将\(y_1,y_2\)颜色\(p\)节点中深度较深的对\(x\)的贡献删除即可。那么我们在合并第二棵线段树时，如果两棵线段树含有相通的叶子结点\([i,i]\)（也就意味着都有颜色\(i\)），那么就将两棵线段树的颜色\(i\)的深度取\(max\)值在\(x\)的第一棵线段树中删除，取\(min\)值作为\(x\)的颜色\(i\)的最小深度。
那么\(x\)的两棵线段树我们都维护好了。\(dfs\)一遍即可求解。
为什么我觉得时间复杂度是\(O(Tm\log^2 n)\)啊。。。网上好像都说是\(O(Tm\log n)\)的。。。
注意事项（调了6h犯的傻逼错误）
- 初始化时千万不要\(memset\)清空线段树，会T飞。
- 查询线段树1的区间和时要判断这个节点是否存在，如果不存在要返回\(0\)，否则会死循环。
- 线段树空间请开到\(10^7\)以上。当然可能\(10^7\)以下是可以过的。
- 每次合并、修改时要新建节点，否则原来节点的信息无法保存。
- 如果您测样例时发现输出了前几个，然后就死循环了，且输出的上一个答案是错的，那么请先找到出错的位置，因为死循环可能是出错后，\(lastans⊕x\)为\(0\)或大于\(n\)。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=500010,M=30000010;
int n,m,T,totel,last,col[N],head[N],rt1[N],rt2[N],dep[N];
struct edge
{
int next,to;
}e[N];
void add(int from,int to)
{
e[++totel].to=to;
e[totel].next=head[from];
head[from]=totel;
}
struct Treenode1
{
int lc,rc,cnt;
};
struct Treenode2
{
int lc,rc,mindep;
};
struct Tree1
{
Treenode1 tree[M];
int tot;
void update(int &x,int l,int r,int k,int val)
{
tree[++tot]=tree[x]; x=tot;
tree[x].cnt+=val;
if (l==k && r==k) return;
int mid=(l+r)>>1;
if (k<=mid) update(tree[x].lc,l,mid,k,val);
else update(tree[x].rc,mid+1,r,k,val);
}
int merge(int x,int y)
{
if (!x || !y) return x+y;
int p=++tot; tree[p]=tree[x];
tree[p].cnt=tree[x].cnt+tree[y].cnt;
tree[p].lc=merge(tree[x].lc,tree[y].lc);
tree[p].rc=merge(tree[x].rc,tree[y].rc);
return p;
}
int ask(int x,int l,int r,int ql,int qr)
{
if (!x) return 0;
if (l==ql && r==qr) return tree[x].cnt;
int mid=(l+r)>>1;
if (qr<=mid) return ask(tree[x].lc,l,mid,ql,qr);
if (ql>mid) return ask(tree[x].rc,mid+1,r,ql,qr);
return ask(tree[x].lc,l,mid,ql,mid)+ask(tree[x].rc,mid+1,r,mid+1,qr);
}
}tree1;
struct Tree2
{
Treenode2 tree[M];
int tot;
void update(int &x,int l,int r,int k,int val)
{
tree[++tot]=tree[x]; x=tot;
if (l==k && r==k)
{
tree[x].mindep=val;
return;
}
int mid=(l+r)>>1;
if (k<=mid) update(tree[x].lc,l,mid,k,val);
else update(tree[x].rc,mid+1,r,k,val);
}
int merge(int x,int y,int l,int r,int root)
{
if (!x || !y) return x+y;
int p=++tot; tree[p]=tree[x];
if (l==r)
{
tree[p].mindep=min(tree[x].mindep,tree[y].mindep);
tree1.update(rt1[root],1,n,max(tree[x].mindep,tree[y].mindep),-1);
}
else
{
int mid=(l+r)>>1;
tree[p].lc=merge(tree[x].lc,tree[y].lc,l,mid,root);
tree[p].rc=merge(tree[x].rc,tree[y].rc,mid+1,r,root);
}
return p;
}
}tree2;
void dfs(int x)
{
tree1.update(rt1[x],1,n,dep[x],1);
tree2.update(rt2[x],1,n,col[x],dep[x]);
for (register int i=head[x];~i;i=e[i].next)
{
dep[e[i].to]=dep[x]+1;
dfs(e[i].to);
rt1[x]=tree1.merge(rt1[x],rt1[e[i].to]);
rt2[x]=tree2.merge(rt2[x],rt2[e[i].to],1,n,x);
}
}
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d%d",&n,&m);
for (register int i=1;i<=n;i++)
rt1[i]=rt2[i]=0,head[i]=-1;
totel=last=tree1.tot=tree2.tot=0; dep[1]=1;
for (register int i=1;i<=n;i++)
scanf("%d",&col[i]);
for (register int i=2,x;i<=n;i++)
{
scanf("%d",&x);
add(x,i);
}
dfs(1);
while (m--)
{
int x,d;
scanf("%d%d",&x,&d);
x^=last; d^=last;
last=tree1.ask(rt1[x],1,n,dep[x],min(dep[x]+d,n));
printf("%d\n",last);
}
}
return 0;
}