简要题意
给定一棵有根树，操作分别为：将某个点到根路径上全部点颜色改为 \(c\)；询问某个点到根路径上不同颜色数。 \(n\le10^5\)
思路
考虑对修改根号重构，那对于某次询问的路径，实际上就是前面有至多 \(\sqrt m\) 个相同颜色段，再拼上后面一段树上的颜色，也就是和修改中点的最深的 \(lca\) ，到这个点这段路径上有多少种不同颜色。
对于前者，我们可以直接暴力统计，再暴力删除重复统计的答案
对于后者，这个问题实际上求的是路径上 \(dep_{lst_{col}}<=dep_{lca}\) 的数的个数，这个东西可以直接用分块维护，插入 \(O(1)\)，查询 \(O(\sqrt n)\)
所以总复杂度为 \(O(n\sqrt n)\)
code
#include<bits/stdc++.h>
using namespace std;
#define N 200005
int n,m,zu,tot,k,top;
int c[N],vis[N],lc[N][19],id[N],dep[N],lg[N],h[N],las[N],f[N],vv[N],lst[N],uu[N];
vector<int> sum[N],qry[N];
vector<pair<int,int> > pos[N];
struct AB{
int a,b,n;
}d[N*2];
void cun(int x,int y){
d[++k]={x,y,h[x]},h[x]=k;
}
struct QUE{
int op,x,y,ans;
}q[N],q1[N];
void DFS(int x,int fa){
dep[x]=dep[fa]+1,lc[++tot][0]=x,id[x]=tot;
for(int i=h[x];i;i=d[i].n){
int y=d[i].b;
DFS(y,x);lc[++tot][0]=x;
}
}
int mn(int x,int y){
return dep[x]<dep[y]?x:y;
}
int Lca(int x,int y){
if(id[x]>id[y]) swap(x,y);
int p=lg[id[y]-id[x]+1];
return mn(lc[id[x]][p],lc[id[y]-(1<<p)+1][p]);
}
struct FenKuai{
int sz,tot;
int c[N],id[N],sum[N],l[N],r[N];
void build(){
sz=sqrt(n);
memset(c,0,sizeof(c));
memset(sum,0,sizeof(sum));
memset(id,0,sizeof(id));
for(int i=0;i<=n;i++){
id[i]=id[max(0,i-sz)]+1;
if(!l[id[i]]) l[id[i]]=i;
r[id[i]]=i,tot=max(tot,id[i]);
}
}
void add(int x,int y){
c[x]+=y,sum[id[x]]+=y;
}
int he(int x){
int i,ans=0;
for(i=1;i<=tot&&r[i]<=x;i++) ans+=sum[i];
for(int j=l[i];j<=x;j++) ans+=c[j];
return ans;
}
}T;
void dfs(int x,int fa){
lst[x]=las[c[x]];
T.add(dep[lst[x]],1);
vis[c[x]]++,las[c[x]]=x;
for(auto p:pos[x]){
int id=p.first,op=p.second;
if(!op){
for(int i=0;i<(int)qry[id].size();i++){
int j=qry[id][i];
sum[id][i]-=vis[q1[j].y];
}
q[id].ans-=T.he(dep[x]);
}
else{
for(int i=0;i<(int)qry[id].size();i++){
int j=qry[id][i];
sum[id][i]+=vis[q1[j].y];
if(sum[id][i]>0) q[id].ans--;
}
q[id].ans+=T.he(dep[q[id].y]);
}
}
for(int i=h[x];i;i=d[i].n){
int y=d[i].b;
dfs(y,x);
}
T.add(dep[lst[x]],-1);
vis[c[x]]--,las[c[x]]=lst[x];
}
void upd(int x,int y){
for(;x&&!vv[x];x=f[x]) c[x]=y,vv[x]=1;
}
void CG(){
for(int i=1;i<=n;i++) vv[i]=0;
for(int i=top;i>=1;i--) upd(q1[i].x,q1[i].y);
}
int main(){
freopen("simple.in","r",stdin);
freopen("simple.out","w",stdout);
scanf("%d",&zu);
while(zu--){
scanf("%d%d",&n,&m);
int sz=sqrt(n)+1;k=0;
memset(h,0,sizeof(h));
for(int i=2,x;i<=n;i++){
scanf("%d",&x);
cun(x,i);f[i]=x;
}
T.build();
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
for(int i=1;i<=m;i++){
scanf("%d%d",&q[i].op,&q[i].x);
if(q[i].op==1) scanf("%d",&q[i].y);
}
tot=0;
DFS(1,0);
for(int i=2;i<=tot;i++) lg[i]=lg[i/2]+1;
for(int j=1;j<=18;j++){
for(int i=1;i+(1<<j)-1<=tot;i++) lc[i][j]=mn(lc[i][j-1],lc[i+(1<<(j-1))][j-1]);
}
int las=0;
for(int i=1;i<=m;i++){
if(q[i].op==1) q1[++top]=q[i];
else{
q[i].y=q[i].ans=0;
for(int j=top;j>=1;j--) uu[q1[j].y]=0;
for(int j=top;j>=1;j--){
int lca=Lca(q[i].x,q1[j].x);
if(dep[lca]>dep[q[i].y]){
if(!uu[q1[j].y]) qry[i].push_back(j),sum[i].push_back(0),q[i].ans++,uu[q1[j].y]=1;
q[i].y=lca;
}
}
pos[q[i].y].push_back({i,0}),pos[q[i].x].push_back({i,1});
}
if(i%sz==0||i==m){
dfs(1,0);
for(int j=las+1;j<=i;j++){
if(q[j].op==2) pos[q[j].x].clear(),pos[q[j].y].clear(),qry[j].clear(),sum[j].clear();
}
CG();
las=i,top=0;
}
}
for(int i=1;i<=m;i++){
if(q[i].op==2) printf("%d\n",q[i].ans);
}
}
return 0;
}