题目链接【http://codeforces.com/problemset/problem/620/E】
题意：给出n个数，每个数有一个初始的颜色。由这n个数组成一颗树。有两种操作1、将以节点u为根的子树的颜色染成k色。2、输出以节点u为根的子树的颜色总数。颜色有60种。
题解：1、用DFS重新对这棵树编号in[u],out[u]表示以节点u为根的子树的区间左右端点。2、用线段树维护更新与查询。3、颜色保存：se每一个二进制位表示一种颜色。0表示没有这种颜色，反之有。
因为有60种颜色，要用LL保存颜色。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+;
vector<int> v[maxn];
int in[maxn],out[maxn];
LL c[maxn];
int n,m;
int id;
void DFS_ORDER(int u)
{
in[u] = ++id;
for(int i = ;i < v[u].size();i++)
{
int w = v[u][i];
if(!in[w]) DFS_ORDER(w);
}
out[u] = id;
}
LL E[maxn*],T[maxn*];//值数组,标记数组
void update(int id,int l,int r,int In,int Out,LL val)
{
if(r < In || l > Out)//不重合
return ;
if(l >= In && Out >= r)//包含
{
E[id] = val;
T[id] = val;
return ;
}
if(T[id])//相交
{
int mid = (l+r)>>;
T[id << ] = T[id];
E[id << ] = T[id];
T[id << | ] = T[id];
E[id << | ] = T[id];
T[id] = ;//取消标记
}
int mid = (l+r) >>;
update(id<<,l,mid,In,Out,val);
update(id<<|,mid+,r,In,Out,val);
E[id] = E[id<<]|E[id<<|];
}
LL query(int id,int l,int r,int In,int Out)
{
if(r < In || l > Out)//不重合
return ;
if(l >= In && Out >= r)//包含
return E[id];
if(T[id])//相交
{
int mid = (l+r)>>;
T[id << ] = T[id];
E[id << ] = T[id];
T[id << | ] = T[id];
E[id << | ] = T[id];
T[id] = ;//取消标记
}
int mid = (l+r) >>;
LL ans1 = query(id<<,l,mid,In,Out);
LL ans2 = query(id<<|,mid+,r,In,Out);
return ans1|ans2;
}
int main ()
{
scanf("%d%d",&n,&m);
for(int i = ;i <= n;i++)
scanf("%lld", &c[i]);
for(int i = ;i <= n-;i++)
{
int u,w;
scanf("%d%d",&u,&w);
v[u].push_back( w );
v[w].push_back( u );
}
DFS_ORDER();
for(int i = ;i <= n;i++)
{
LL x = LL()<<(c[i]-);
update(,,n,in[i],in[i],x);
}
int ty,u;LL val;
for(int i = ;i <= m;i++)
{
scanf("%d",&ty);
if(ty == )
{
scanf("%d%lld",&u,&val);
LL x = LL()<<(val-);
update(,,n,in[u],out[u],x);
}
else
{
scanf("%d",&u);
LL t = query(,,n,in[u],out[u]);
int ans=;
while(t){if(t&)ans++;t>>=;}
printf("%d\n",ans);
}
}
return ;
}