P9076
Ynoi Easy Round ，但我这个采购调了一个上午。
考虑朴素的做法，用并查集维护最大同色联通块，更改颜色时，将所有同色的儿子合并上去，儿子的儿子成为了新连通块的儿子，这个可以用 set 维护插入，删除，合并。然后再将自己尝试并到父亲上。瓶颈在于查询有多少个同色的儿子。
考虑优化找儿子的过程，发现你可以用线段树维护每个节点的儿子颜色区间，颜色区间的叶子上存一个链表，链表存这个颜色的儿子是哪些。那你可以直接动态开点主席树，合并的时候直接在线段树上递归合并，如果递归到叶子，就把两个链表合并起来。查询时直接找到对应的叶子，在链表上跳即可。复杂度均摊应该是对的。
实现细节有点多，可以去看代码，如果看不懂可以私信。
感谢 @ExplodingKonjac 给我们带来的毒瘤。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+10;
int fat[maxn],n,m;
struct edge{int to,next;}E[maxn];
int head[maxn],TOT;
inline void add(int u,int v)
{
E[++TOT]={v,head[u]};
head[u]=TOT;
}
struct node{int id,fr,to;}N[maxn*2];
int cnt=0;
int ls[maxn*30],rs[maxn*30],fir[maxn*30],ed[maxn*30];
int tot;
void update(int &i,int l,int r,int p,int v)
{
if(!i)i=++tot;
if(l==r)
{
N[++cnt].id=v;
N[cnt].to=fir[i];
N[fir[i]].fr=cnt;
if(!fir[i])ed[i]=cnt;
fir[i]=cnt;
return;
}
int mid=l+r>>1;
if(p<=mid)update(ls[i],l,mid,p,v);
else update(rs[i],mid+1,r,p,v);
}
void print(int x){for(int h=fir[x];h;h=N[h].to)printf("%d ",N[h].id);putchar('\n');}
int merge(int i,int j,int l,int r)
{
if(!i||!j)return i|j;
if(l==r)
{
// printf("I :");print(i);
// printf("J :");print(j);
if(!fir[i])
{
fir[i]=fir[j];
ed[i]=ed[j];
}
else if(!fir[j]);
else
{
N[ed[i]].to=fir[j];
N[fir[j]].fr=ed[i];
ed[i]=ed[j];
}
return i;
}
int mid=l+r>>1;
ls[i]=merge(ls[i],ls[j],l,mid);
rs[i]=merge(rs[i],rs[j],mid+1,r);
return i;
}
int query(int i,int l,int r,int p)
{
if(!i)return 0;
if(l==r)return i;
int mid=l+r>>1;
if(p<=mid)return query(ls[i],l,mid,p);
else return query(rs[i],mid+1,r,p);
}
int rt[maxn],col[maxn];
int par[maxn],siz[maxn];
int find(int x){return x==par[x]?x:par[x]=find(par[x]);}
void dfs(int u)
{
for(int i=head[u];i;i=E[i].next)
{
int v=E[i].to;
dfs(v);
}
vector<int> S,T;
for(int i=head[u];i;i=E[i].next)
{
int v=E[i].to;
v=find(v);
if(col[u]==col[v])
S.push_back(v);
else T.push_back(v);
}
u=find(u);
for(int v:S)rt[u]=merge(rt[u],rt[v],1,1000000),par[v]=u,siz[u]+=siz[v];
for(int v:T)update(rt[u],1,1000000,col[v],v);
}
int vis[maxn];
int main()
{
//freopen("data3.in","r",stdin);
//freopen("b3.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=2;i<=n;i++)
scanf("%d",&fat[i]),add(fat[i],i);
for(int i=1;i<=n;i++)
scanf("%d",&col[i]);
for(int i=1;i<=n;i++)par[i]=i,siz[i]=1;
dfs(1);
for(int t=1;t<=m;t++)
{
int opt,x,y;
scanf("%d",&opt);
if(opt==2)
{
scanf("%d",&x);
printf("%d\n",siz[find(x)]);
}
else
{
scanf("%d%d",&x,&y);
x=find(x);
if(col[x]==y)continue;
int now=query(rt[x],1,1000000,y);
if(now)
{
vector<int> son;
for(int h=fir[now];h;h=N[h].to)
{
int s=N[h].id;
s=find(s);
if(col[s]==y&&vis[s]!=t&&s!=x)son.push_back(s),vis[s]=t;
}
fir[now]=ed[now]=0;
for(int s:son)
{
//printf("!%d\n",s);
rt[x]=merge(rt[x],rt[s],1,1000000);
siz[x]+=siz[s];
par[s]=x;
}
}
if(fat[x])
{
int F=find(fat[x]);
if(y==col[F])
{
par[x]=F;
siz[F]+=siz[x];
//printf("?%d %d\n",F,x);
merge(rt[F],rt[x],1,1000000);
}
else update(rt[F],1,1000000,y,x);
}
col[x]=y;
}
}
return 0;
}