CF620E New Year Tree
题目描述
The New Year holidays are over, but Resha doesn't want to throw away the New Year tree. He invited his best friends Kerim and Gural to help him to redecorate the New Year tree.
The New Year tree is an undirected tree with nn vertices and root in the vertex 11 .
You should process the queries of the two types:
- Change the colours of all vertices in the subtree of the vertex vv to the colour cc .
- Find the number of different colours in the subtree of the vertex vv .
输入格式
The first line contains two integers n,mn,m ( 1<=n,m<=4·10^{5}1<=n,m<=4⋅105 ) — the number of vertices in the tree and the number of the queries.
The second line contains nn integers c_{i}c**i ( 1<=c_{i}<=601<=c**i<=60 ) — the colour of the ii -th vertex.
Each of the next n-1n−1 lines contains two integers x_{j},y_{j}x**j,y**j ( 1<=x_{j},y_{j}<=n1<=x**j,y**j<=n ) — the vertices of the jj -th edge. It is guaranteed that you are given correct undirected tree.
The last mm lines contains the description of the queries. Each description starts with the integer t_{k}t**k ( 1<=t_{k}<=21<=t**k<=2 ) — the type of the kk -th query. For the queries of the first type then follows two integers v_{k},c_{k}v**k,c**k ( 1<=v_{k}<=n,1<=c_{k}<=601<=v**k<=n,1<=c**k<=60 ) — the number of the vertex whose subtree will be recoloured with the colour c_{k}c**k . For the queries of the second type then follows integer v_{k}v**k ( 1<=v_{k}<=n1<=v**k<=n ) — the number of the vertex for which subtree you should find the number of different colours.
输出格式
For each query of the second type print the integer aa — the number of different colours in the subtree of the vertex given in the query.
Each of the numbers should be printed on a separate line in order of query appearing in the input.
题意翻译
你有一棵以1为根的有根树，有n个点，每个节点初始有一个颜色c[i]。
有两种操作：
1 v c 将以v为根的子树中所有点颜色更改为c
2 v 查询以v为根的子树中的节点有多少种不同的颜色
翻译贡献者UID：28455
输入输出样例
输入 #1复制
输出 #1复制
输入 #2复制
输出 #2复制
题解：
来水一发其他大佬都没提到过的题解：
bitset+半树链剖分
知识铺垫：
对(bitset)容器不太了解的小伙伴请戳这里：
对树链剖分不太了解的小伙伴请戳这里：
2019.10.29模拟赛T3 50分场
一开始觉得用树链剖分可做，想得很简单，后来代码实现的时候碰到一堆问题。冥思苦想很长时间之后，用搜索统计拿到了50分：
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=8*1e5+10;
int n,m;
int a[maxn];
int tot,head[maxn],nxt[maxn<<1],to[maxn<<1],fa[maxn];
bool vis[70];
void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void update(int x,int k)
{
a[x]=k;
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==fa[x])
continue;
update(y,k);
}
}
int query(int x)
{
int ret=0;
if(!vis[a[x]])
{
vis[a[x]]=1;
ret++;
}
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==fa[x])
continue;
ret+=query(y);
}
return ret;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
fa[v]=u;
}
for(int i=1;i<=m;i++)
{
int opt;
scanf("%d",&opt);
int v,c;
if(opt==1)
{
scanf("%d%d",&v,&c);
update(v,c);
}
else
{
scanf("%d",&v);
memset(vis,0,sizeof(vis));
printf("%d
",query(v));
}
}
return 0;
}
后来看到正解是用状态压缩加DFS序转线段树过的。
我没有改变正解的思路，只是在实现方式上变了一下花样。
大家是用long long进行状压的。我使用了bitset容器。大家是用DFS记录了DFS序的两个时间戳进行查询/修改的。我使用的是树链剖分预处理操作中的size数组进行实现的。
思路：输入数据建立原始树，然后在进行两次DFS（一次当然可以，但因为我直接用的树链剖分的板子，就懒得改了）跑出size数组和id、idx数组，这两个数组构建了一个完整、可复的映射关系。然后以此建立线段树。其中bitset容器的每位表示这种颜色有还是没有，所以最后只需要统计bitset容器中1的个数就可以。省去了用lowbit运算进行数1的操作。
对于线段树的更新，我们采用了位运算中的或运算，根据bitset容器的性质，或运算是可以应用于bitset容器上的，就成功地把线段树的两个状态合并到一起。
对于线段树的查询/修改区间，很明显，它在区间上的范围就是([id[x],id[x]+size[x]-1])，如有不懂请参照上面的树链剖分博客补习。
完整AC代码：
#include<cstdio>
#include<bitset>
#define lson pos<<1
#define rson pos<<1|1
using namespace std;
const int maxn=4*1e5+10;
char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int read()
{
int x=0;
char ch=nc();
while(ch>47)
x=(((x<<2)+x)<<1)+ch-48,ch=nc();
return x;
}
int n,m,a[maxn],cnt;
int tot,head[maxn],nxt[maxn<<1],to[maxn<<1];
int fa[maxn],id[maxn],idx[maxn],size[maxn];
int lazy[maxn<<2];
bitset<64> tree[maxn<<2];
void add(int x,int y)
{
to[++tot]=y;
nxt[tot]=head[x];
head[x]=tot;
}
void dfs1(int x,int f)
{
fa[x]=f;
size[x]=1;
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==f)
continue;
dfs1(y,x);
size[x]+=size[y];
}
}
void dfs2(int x)
{
id[x]=++cnt;
idx[cnt]=x;
for(int i=head[x];i;i=nxt[i])
{
int y=to[i];
if(y==fa[x])
continue;
dfs2(y);
}
}
void build(int pos,int l,int r)
{
int mid=(l+r)>>1;
if(l==r)
{
tree[pos].set(a[idx[l]]);
return;
}
build(lson,l,mid);
build(rson,mid+1,r);
tree[pos]=tree[lson]|tree[rson];
}
void mark(int pos,int l,int r,int k)
{
lazy[pos]=k;
tree[pos].reset();
tree[pos].set(k);
}
void pushdown(int pos,int l,int r)
{
int mid=(l+r)>>1;
if(!lazy[pos])
return;
mark(lson,l,mid,lazy[pos]);
mark(rson,mid+1,r,lazy[pos]);
lazy[pos]=0;
}
void update(int pos,int l,int r,int x,int y,int k)
{
int mid=(l+r)>>1;
if(x<=l && r<=y)
{
mark(pos,l,r,k);
return;
}
pushdown(pos,l,r);
if(x<=mid)
update(lson,l,mid,x,y,k);
if(y>mid)
update(rson,mid+1,r,x,y,k);
tree[pos]=tree[lson]|tree[rson];
}
bitset<64> query(int pos,int l,int r,int x,int y)
{
int mid=(l+r)>>1;
bitset<64> ret;
if(x<=l && r<=y)
return tree[pos];
pushdown(pos,l,r);
if(x<=mid)
ret|=query(lson,l,mid,x,y);
if(y>mid)
ret|=query(rson,mid+1,r,x,y);
return ret;
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
a[i]=read();
for(int i=1;i<n;i++)
{
int u,v;
u=read(),v=read();
add(u,v);
add(v,u);
}
dfs1(1,0);
dfs2(1);
build(1,1,n);
for(int i=1;i<=m;i++)
{
int opt,v,c;
opt=read();
if(opt==1)
{
v=read();c=read();
update(1,1,n,id[v],id[v]+size[v]-1,c);
}
else
{
v=read();
printf("%d
",query(1,1,n,id[v],id[v]+size[v]-1).count());
}
}
return 0;
}