題意:給你一顆樹 (一開始染好色的) 給你兩種操作 一種是把目前節點和他的子樹染成同一種顔色 還有一種是查詢他和他的子樹 到底有多少種不同的顔色?
思路:假設 他是一根直線 那麼就是線段樹 區間操作染色 中間合并就是或操作即可 因為他的染色方案不多 但是轉換成一棵樹的話 我們先進行一次深搜 由于深搜方式可以使得他和他的子節點的編号是連續的 是以就可以使用直線的方法
一開始 看題是對樹的區間劃分 聯想到了樹鍊刨分 由于給了祖先 就不需要分重鍊和輕鍊 然後就 。。。
#include<stdio.h>
#include<string.h>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
#define N 400100
#define LL long long
LL c[N*4];
LL p[N*4];
LL a[N];
int siz[N],id[N],cnt,h[N];
void pushdown(int tt)
{
int l=tt*2,r=tt*2+1;
if(p[tt])
{
c[l]=c[r]=p[l]=p[r]=p[tt];
p[tt]=0;
}
c[tt]=c[l]|c[r];
}
void build(int l,int r,int tt)
{
if(l==r)
{
c[tt]=a[h[l]];
return ;
}
int mid=(l+r)/2;
build(l,mid,tt*2);
build(mid+1,r,tt*2+1);
pushdown(tt);
}
vector<int> e[N];
void dfs(int x,int fa)
{
id[x]=++cnt;
for(int i=0;i<e[x].size();i++)
{
int to=e[x][i];
if(to==fa)continue;
dfs(to,x);
siz[x]+=1+siz[to];
}
}
LL query(int l,int r,int tt,int x,int y)
{
if(l==x&&r==y)
return c[tt];
pushdown(tt);
int mid=(l+r)/2;
if(mid>=y)
return query(l,mid,tt*2,x,y);
else if(mid<x)
return query(mid+1,r,tt*2+1,x,y);
else
return query(l,mid,tt*2,x,mid)|query(mid+1,r,tt*2+1,mid+1,y);
}
void update(int l,int r,int x,int y,int tt,LL z)
{
if(l==x&&r==y)
{
p[tt]=c[tt]=z;
return ;
}
pushdown(tt);
int mid=(l+r)/2;
if(x>mid)
update(mid+1,r,x,y,tt*2+1,z);
else if(y<=mid)
update(l,mid,x,y,tt*2,z);
else
{
update(mid+1,r,mid+1,y,tt*2+1,z);
update(l,mid,x,mid,tt*2,z);
}
c[tt]=c[tt*2]|c[tt*2+1];
}
int getAns(LL x)
{
int sum=0;
while(x)
{
sum+=(x%2);
x/=2;
}
return sum;
}
int main()
{
int n,m,u,v,op;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
a[i]=(1LL)<<a[i];
}
for(int i=1;i<n;i++)
{
scanf("%d%d",&u,&v);
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1,1);
for(int i=1;i<=n;i++)
h[id[i]]=i;
build(1,n,1);
for(int i=0;i<m;i++)
{
scanf("%d",&op);
if(op==1)
{
scanf("%d%d",&u,&v);
LL x=(1LL)<<v;
update(1,n,id[u],id[u]+siz[u],1,x);
}
else
{
scanf("%d",&u);
printf("%d\n",getAns(query(1,n,1,id[u],id[u]+siz[u])));
}
}
return 0;
}