codeforces 620e

题意：给你一颗树 （一开始染好色的） 给你两种操作 一种是把当前节点和他的子树染成同一种颜色 还有一种是查询他和他的子树 到底有多少种不同的颜色？

思路：假设 他是一根直线 那么就是线段树 区间操作染色 中间合并就是或操作即可 因为他的染色方案不多  但是转换成一棵树的话  我们先进行一次深搜 由于深搜方式可以使得他和他的子节点的编号是连续的 所以就可以使用直线的方法

一开始  看题是对树的区间划分  联想到了树链刨分 由于给了祖先  就不需要分重链和轻链 然后就 。。。

#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;
}