hdu5709-Claris Loves Painting【线段树合并】

正题

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

题目大意

$n$个点的一棵树，每次有询问$(u,k)$表在$u$的子树中，距离$u$不超过$k$的节点中有多少不同颜色的节点。

解题思路

线段树维护每个深度有多少是颜色出现的最浅的位置，发现这样无法线段树合并，因为每次合并会有多个重复的。所以我们还要再维护一个线段树表示每个颜色第一次出现的位置，然后在合并这颗的时候可以把第一课的给去重了。

因为要预处理的是所有的子树的线段树，所以每次合并和修改（和主席树一样）都要新建节点。

时间复杂度$O((n+q)\log n)$

$code$

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=5e5+10,M=3e7+10;
struct node{
    int to,next;
}a[N];
int T,n,q,c[N],dep[N],ls[N],rt1[N],rt2[N],tot;
struct Seq_Tree1{
    int cnt,ls[M],rs[M],w[M];void Change(int &x,int L,int R,int pos,int val){
    ++cnt;ls[cnt]=ls[x];rs[cnt]=rs[x];w[cnt]=w[x]+val;x=cnt;if(L==R)return;int mid=(L+R)>>1;if(pos<=mid)Change(ls[x],L,mid,pos,val);else Change(rs[x],mid+1,R,pos,val);return;}int Ask(int x,int L,int R,int l,int r){
    if(!x)return 0;if(L==l&&R==r)return w[x];int mid=(L+R)>>1;if(r<=mid)return Ask(ls[x],L,mid,l,r);if(l>mid)return Ask(rs[x],mid+1,R,l,r);return Ask(ls[x],L,mid,l,mid)+Ask(rs[x],mid+1,R,mid+1,r);}int Merge(int x,int y){
    if(!x||!y)return x+y;int now=++cnt;w[now]=w[x]+w[y];ls[now]=Merge(ls[x],ls[y]);rs[now]=Merge(rs[x],rs[y]);return now;}
}T1;
struct Seq_Tree2{
    int cnt,ls[M],rs[M],w[M];void Change(int &x,int L,int R,int pos,int val){
    if(!x)x=++cnt,ls[x]=rs[x]=w[x]=0;if(L==R){
    w[x]=val;return;}int mid=(L+R)>>1;if(pos<=mid)Change(ls[x],L,mid,pos,val);else Change(rs[x],mid+1,R,pos,val);return;}int Merge(int x,int y,int L,int R,int rt){
    if(!x||!y)return x+y;int now=++cnt;if(L==R){
    T1.Change(rt1[rt],1,n,max(w[x],w[y]),-1);w[now]=min(w[x],w[y]);return now;}int mid=(L+R)>>1;ls[now]=Merge(ls[x],ls[y],L,mid,rt);rs[now]=Merge(rs[x],rs[y],mid+1,R,rt);return now;}
}T2;
void addl(int x,int y){
    a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return;
}
void dfs(int x){
    rt1[x]=rt2[x]=0;T1.Change(rt1[x],1,n,dep[x],1);T2.Change(rt2[x],1,n,c[x],dep[x]); for(int i=ls[x];i;i=a[i].next){
    int y=a[i].to;dep[y]=dep[x]+1;dfs(y);rt1[x]=T1.Merge(rt1[x],rt1[y]);rt2[x]=T2.Merge(rt2[x],rt2[y],1,n,x);}return;
}
int main()
{
    scanf("%d",&T);while(T--){
    T1.cnt=T2.cnt=tot=0; scanf("%d%d",&n,&q);for(int i=1;i<=n;i++)scanf("%d",&c[i]),ls[i]=0;for(int i=2;i<=n;i++){
    int x;scanf("%d",&x);addl(x,i);}dep[1]=1;dfs(1);int last=0;while(q--){
    int u,k;scanf("%d%d",&u,&k);u^=last;k^=last;printf("%d\n",last=T1.Ask(rt1[u],1,n,dep[u],min(dep[u]+k,n)));}}
}