codeforces-620E-New Year Tree

 

因为一个该死的学弟,让我去打这道题,然后妥妥的浪费了我不知道几个小时,然后这个早上心态爆炸。。。然后,不想写题解。。。

传送门

题意:

给你一个染了色的树,然后给你n-1条树边,有两个操作,一个是把给定节点的那棵子树染成指定颜色,二是询问一颗子树的颜色种类。。。

分析:

点和边数都是4e5大小的,但是颜色只有60种,所以我们可以直接用二进制来保存状态,我们考虑一个神奇的东西,叫dfs序,他可以在知道子树大小的情况下找到子树的所有节点。。。我们想,可以在dfs序上建一棵线段树,然后进行区间修改和查询就好了。。。好的那么代码就很简单了(简单个屁)。。。

然后我并不是很会线段树,然后就打了一个very long very翔的treap,来模拟线段树。。。

然后,就调了不知道多久,写这篇博客的时候,作者已经升天了。。。

代码:(谨慎观看)

 

#include<bits/stdc++.h>
#define LL long long
#define int LL
using namespace std;
const LL N=4e5+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f;
namespace FastIO
{
    template<typename tp> inline void read(tp &x)
    {
        x=0; register char c=getchar(); register bool f=0;
        for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
        for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
        if(f) x=-x;
    }
    template<typename tp> inline void write(tp x)
    {
        if (x==0) return (void) (putchar('0'));
        if (x<0) putchar('-'),x=-x;
        LL pr[20]; register LL cnt=0;
        for (;x;x/=10) pr[++cnt]=x%10;
        while (cnt) putchar(pr[cnt--]+'0');
    }
    template<typename tp> inline void writeln(tp x)
    {
        write(x);
        putchar('\n');
    }
}
using namespace FastIO;
struct node
{
    LL sum,add,size,key,p;
    node *ch[2];
}*root;
node *new_node(LL x)
{
    node *y=new node;
    y->key=y->sum=x;
    y->ch[0]=y->ch[1]=NULL;
    y->size=1,y->add=0;
    y->p=rand();
    return y;
}
LL sum_of(node *x)
{
    if(x==NULL) return 0;
    else return x->sum;
}
LL size_of(node *x)
{
    if(x==NULL) return 0;
    else return x->size;
}
void update(node *x)
{
    x->sum=sum_of(x->ch[0])|(sum_of(x->ch[1])|x->key);
    x->size=size_of(x->ch[0])+size_of(x->ch[1])+1;
}
void push_down(node *x)
{
    if(x->add==0)
        return;
    if(x->ch[0]!=NULL)
    {
        x->ch[0]->key=x->add;
        x->ch[0]->add=x->add;
        x->ch[0]->sum=x->add;
    }
    if(x->ch[1]!=NULL)
    {
        x->ch[1]->key=x->add;
        x->ch[1]->add=x->add;
        x->ch[1]->sum=x->add;
    }
    x->add=0;
}
node *merge(node *x,node *y)
{
    if(x==NULL)
        return y;
    if(y==NULL)
        return x;
    if(y->p>x->p)
    {
        push_down(x);
        x->ch[1]=merge(x->ch[1],y);
        update(x);
        return x;
    }
    else
    {
        push_down(y);
        y->ch[0]=merge(x,y->ch[0]);
        update(y);
        return y;
    }
}
void split(node *now,node *&x,node *&y,int k)
{
    if(now==NULL)
    {
        x=NULL,y=NULL;
        return;
    }
    push_down(now);
    if(size_of(now->ch[0])+1<=k)
    {
        x=now;
        split(now->ch[1],now->ch[1],y,k-size_of(now->ch[0])-1);
    }
    else
    {
        y=now;
        y=now;
        split(now->ch[0],x,now->ch[0],k);
    }
    update(now);
}
int n,m;
node *x,*y,*z,*w;
int head[N],cnt=-1;
int col[N],siz[N],zz[N];
vector<int> vec;
struct Edge{int next,to;}edge[N*2];
void add(int from,int to)
{
    edge[++cnt].to=to;
    edge[cnt].next=head[from];
    head[from]=cnt;
}
void dfs(int now,int fa)
{
    siz[now]=1;vec.push_back(now);
    for(int i=head[now];i!=-1;i=edge[i].next)
    {
        int to=edge[i].to;
        if(to==fa)continue;
        dfs(to,now);
        siz[now]+=siz[to];
    }
}
main()
{
    read(n),read(m);
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n;i++)
        read(col[i]);
    for(int i=1,l,r;i<n;i++)
        read(l),read(r),add(l,r),add(r,l);
    dfs(1,0);
    for(int i=0;i<n;i++)
    {
        root=merge(root,new_node((1LL<<(col[vec[i]]-1))));
        zz[vec[i]]=i+1;
    }
    for(int i=1;i<=m;i++)
    {
        int flag;read(flag);
        if(flag==1)
        {
            LL rt,k;read(rt),read(k);
            split(root,x,y,zz[rt]+siz[rt]-1);
            split(x,z,w,zz[rt]-1);
            k=(1LL<<(k-1));w->add=k;
            w->key=k;w->sum=k;
            root=merge(merge(z,w),y);
        }
        else
        {
            LL rt,ret=0;read(rt);
            split(root,x,y,zz[rt]+siz[rt]-1);
            split(x,z,w,zz[rt]-1);
            for(int j=0;j<60;j++)
                if((sum_of(w)&((LL)(1LL<<j)))>0)
                    ret++;
            writeln(ret);
            root=merge(merge(z,w),y);
        }
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注