【主席树】Claris Loves Painting

主席树, 线段树

传送门：HDU5709

题意：给定一棵有根树，每条边长度均为1；

每个结点有1个颜色，多次询问以某结点为根且与某它距离不超过x的子树中有几种颜色；

强制在线；

思路：

不考虑距离限制，把树化成DFS序；

那么每个点加进来会使该点 到 dfs序上与它相邻的同色点与它的LCA 这条路径上（不包括LCA）多一个颜色；

由于是dfs序，可以用线段树维护；

如果考虑距离限制，答案为把深度小于等于deep+dist的点加进来时的答案，可用主席树；

注意：

按照深度加点，dfs序上相邻的点是已经加进来的点，可用set维护 注意初始化的时间复杂度；

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
using namespace std;
#define N 300000
int t,n,m,clock,tot,tot2,tot3,x,d,ans,MAX;
int a[N],dfn[N],deep[N],top[N],fa[N],size[N],head[N],fin[N],DFS[N];
int sum[N*21],ls[N*21],rs[N*21],rt[N],q[N],pos[N];
set< pair<int,int> > s;
struct edge{int v,nxt;}e[N];
void init(int n){
    clock=tot=tot2=tot3=ans=MAX=0;
    for (int i=0;i<=n*2*20;i++) sum[i]=ls[i]=rs[i]=0;
    memset(rt,0,sizeof rt);    memset(pos,0,sizeof pos);
    memset(dfn,0,sizeof dfn); memset(head,0,sizeof head);
    memset(deep,0,sizeof deep); memset(top,0,sizeof top);
    memset(fin,0,sizeof fin); memset(sum,0,sizeof sum);
    memset(e,0,sizeof e); memset(size,0,sizeof size);
}
void add(int x,int y){e[++tot].v=y; e[tot].nxt=head[x]; head[x]=tot;}
void dfs1(int cur){
    dfn[cur]=++clock; DFS[clock]=cur; fin[cur]=dfn[cur];
    deep[cur]=deep[fa[cur]]+1; size[cur]=1;
    for (int i=head[cur];i;i=e[i].nxt){
        dfs1(e[i].v); size[cur]+=size[e[i].v];
        fin[cur]=fin[e[i].v];
    }
}
void dfs2(int cur){
    if (!top[cur]) top[cur]=cur;
    int t=0;
    for (int i=head[cur];i;i=e[i].nxt) if (size[e[i].v]>size[t]) t=e[i].v;
    if (!t) return; top[t]=top[cur]; dfs2(t);
    for (int i=head[cur];i;i=e[i].nxt) if (e[i].v!=t) dfs2(e[i].v);
}
int lca(int u,int v){
    for (;top[u]!=top[v];u=fa[top[u]]) if (deep[top[u]]<deep[top[v]]) swap(u,v);
    return deep[u]<deep[v]?u:v;
}
void add(int &root,int root2,int l,int r,int k,int s){
    if (!root) root=++tot2; sum[root]=sum[root2]+s;
    if (l==r) return;
    int mid=(l+r)>>1;
    if (k<=mid){rs[root]=rs[root2]; add(ls[root],ls[root2],l,mid,k,s);}
    if (k>mid){ls[root]=ls[root2]; add(rs[root],rs[root2],mid+1,r,k,s);}
}
int query(int root,int l,int r,int L,int R){
    if (!root) return 0;
    if (L<=l && R>=r) return sum[root];
    int mid=(l+r)>>1,tmp=0;
    if (L<=mid) tmp+=query(ls[root],l,mid,L,R);
    if (R>mid) tmp+=query(rs[root],mid+1,r,L,R);
    return tmp;
}
int main(){
    scanf("%d",&t);
    while (t--){
        init(n);
        
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++) scanf("%d",&a[i]);
        for (int i=2;i<=n;i++){scanf("%d",&fa[i]); add(fa[i],i);}
        
        dfs1(1); dfs2(1);
        
        int tt=0,ww=1; q[1]=1; s.clear();
        while (tt<ww){
            int u=q[++tt];
            tot3++; add(rt[tot3],rt[tot3-1],1,n,dfn[u],1);
            int LCA=0;
            if (s.lower_bound(make_pair(a[u],dfn[u]))!=s.begin()){
                pair<int,int> tmp=*(--s.lower_bound(make_pair(a[u],dfn[u])));
                if (tmp.first==a[u] && deep[LCA]<deep[lca(u,DFS[tmp.second])]) LCA=lca(u,DFS[tmp.second]);
            }
            if (s.upper_bound(make_pair(a[u],dfn[u]))!=s.end()){
                pair<int,int> tmp=*s.upper_bound(make_pair(a[u],dfn[u]));
                if (tmp.first==a[u] && deep[LCA]<deep[lca(u,DFS[tmp.second])]) LCA=lca(u,DFS[tmp.second]);
            }
            if (LCA){tot3++; add(rt[tot3],rt[tot3-1],1,n,dfn[LCA],-1);}
            pos[deep[u]]=tot3; MAX=max(deep[u],MAX);
            s.insert(make_pair(a[u],dfn[u]));
            for (int i=head[u];i;i=e[i].nxt) q[++ww]=e[i].v;
        }        
        for (int i=1;i<=m;i++){
            scanf("%d%d",&x,&d); x^=ans; d^=ans; 
            int tmp=min(deep[x]+d,MAX);
            printf("%d\n",ans=query(rt[pos[tmp]],1,n,dfn[x],fin[x]));
        }
    }
    return 0;
}