New Year Tree

回去再调.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+5;
ll col[N];
vector<int>g[N];
int now[N],last[N],id=0,sz[N];//这个数组之前是x的现在节点id是谁.现在是id,对应之前x是多少.
struct seg{
    ll l,r,sum,lazy;
}tr[N<<2];
void dfs(int u,int fa)
{
    now[u]=++id;last[id]=u;
    sz[u]=1;
    for(int x:g[u])
    {
        if(x==fa)    continue;
        dfs(x,u);sz[u]+=sz[x];
    }
}

void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum|tr[u<<1|1].sum;
}

void pushdown(int u)
{
    if(tr[u].lazy)
    {
        tr[u<<1|1].lazy=tr[u<<1].lazy=tr[u].lazy;tr[u].lazy=0;
        tr[u<<1].sum=tr[u<<1|1].sum=(1ll<<(tr[u].lazy-1));
    }
}

void build(int u,int l,int r)//我拿1~n建树.
{
    tr[u].l=l,tr[u].r=r;
    if(l==r)
    {
        tr[u].sum=(1ll<<col[last[l]]);
        return ;
    }int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

void modify(int u,int l,int r,int val)//实行操作1.
{
    int L=tr[u].l,R=tr[u].r;
    if(r<L||l>R)    return;
    pushdown(u);
    if(l<=L&&r>=R)
    {
        tr[u].lazy=val;
        tr[u].sum=(1ll<<(val-1));
    }
    modify(u<<1,l,r,val);
    modify(u<<1|1,l,r,val);
    pushup(u);
}

int query(int u,int l,int r)//询问[l,r]区间的或值.
{
    int L=tr[u].l,R=tr[u].r;
    if(r<L||l>R)    return 0;
    pushdown(u);
    if(l<=L&&r>=R)
    {
        return tr[u].sum;
    }return query(u<<1,l,r)+query(u<<1|1,l,r);

}

int ans(ll u)//统计下二进制下有多少个1~
{
    int res=0;
    for(ll i=0;i<=60;i++)
    {
        if(u>>i&1)    res++;
    }return res;
}

int main()
{
    //输入!
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)    scanf("%lld",&col[i]);
    for(int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    //树链剖分!
    dfs(1,1);
    build(1,1,n);
    //询问!
    while(m--)
    {
        int op;scanf("%d",&op);
        if(op==1)
        {
            int x,y;scanf("%d%d",&x,&y);
            //改变x子树颜色全部改成y.
            modify(1,now[x],now[x]+sz[x]-1,y);
        }
        else
        {
            int x;scanf("%d",&x);
            //询问x点子树有多少不同的颜色.
            printf("%d\n",ans(query(1,now[x],now[x]+sz[x]-1)));
        }
    }
    return 0;
}

(⊙o⊙)…改好了,细节错了忆点而已~
具体思路视频都讲了~
ac代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=4e5+5;
ll col[N];
vector<int>g[N];
int now[N],last[N],id=0,sz[N];//这个数组之前是x的现在节点id是谁.现在是id,对应之前x是多少.
struct seg{
    ll l,r,sum,lazy;
}tr[N<<3];
void dfs(int u,int fa)
{
    now[u]=++id;last[id]=u;
    sz[u]=1;
    for(int x:g[u])
    {
        if(x==fa)    continue;
        dfs(x,u);sz[u]+=sz[x];
    }
}

void pushup(int u)
{
    tr[u].sum=tr[u<<1].sum|tr[u<<1|1].sum;
}

void pushdown(int u)
{
    if(tr[u].lazy)
    {
        tr[u<<1|1].lazy=tr[u<<1].lazy=tr[u].lazy;
        tr[u<<1].sum=tr[u<<1|1].sum=(1ll<<(tr[u].lazy-1));
        tr[u].lazy=0;
    }
}

void build(int u,int l,int r)//我拿1~n建树.
{
    tr[u].l=l,tr[u].r=r;
    if(l==r)
    {
        tr[u].sum=(1ll<<(col[last[l]]-1));
        return ;
    }int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
    pushup(u);
}

void modify(int u,int l,int r,int val)//实行操作1.
{
    int L=tr[u].l,R=tr[u].r;
    if(r<L||l>R)    return;
    pushdown(u);
    if(l<=L&&r>=R)
    {
        tr[u].lazy=val;
        tr[u].sum=(1ll<<(val-1));
        return;
    }
    modify(u<<1,l,r,val);
    modify(u<<1|1,l,r,val);
    pushup(u);
}

ll query(int u,int l,int r)//询问[l,r]区间的或值.
{
    int L=tr[u].l,R=tr[u].r;
    if(r<L||l>R)    return 0;
    pushdown(u);
    if(l<=L&&r>=R)
    {
        return tr[u].sum;
    }return query(u<<1,l,r)|query(u<<1|1,l,r);

}

int ans(ll u)//统计下二进制下有多少个1~
{
    int res=0;
    for(ll i=0;i<=60;i++)
    {
        if(u>>i&1)    res++;
    }return res;
}

int main()
{
    //输入!
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)    scanf("%lld",&col[i]);
    for(int i=1;i<n;i++)
    {
        int u,v;scanf("%d%d",&u,&v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    //树链剖分!
    dfs(1,1);
    build(1,1,n);
    //询问!
    while(m--)
    {
        int op;scanf("%d",&op);
        if(op==1)
        {
            int x,y;scanf("%d%d",&x,&y);
            //改变x子树颜色全部改成y.
            modify(1,now[x],now[x]+sz[x]-1,y);
        }
        else
        {
            int x;scanf("%d",&x);
            //询问x点子树有多少不同的颜色.
            printf("%d\n",ans(query(1,now[x],now[x]+sz[x]-1)));
        }
    }
    return 0;
}