【CF620E】New Year Tree

（题面来自luogu）

题意翻译

你有一棵以1为根的有根树，有n个点，每个节点初始有一个颜色c[i]。

有两种操作：

1 v c 将以v为根的子树中所有点颜色更改为c

2 v 查询以v为根的子树中的节点有多少种不同的颜色

翻译贡献者UID：28455

n、m <= 4e5，ci <= 60。

　　今天唯一听懂的一道题目，调了两个小时……因为要查询子树信息，考虑构造出dfs序之后，用线段树维护区间颜色。因为颜色只有60种，可以维护在节点上维护bitset或者一个64位整型来压缩状态，每一位上表示以该点为根的子树内是否含有这个颜色。

　　线段树内的tag是不可以累加的，每个tag都是一次直接修改，因此要在下推时特判掉空的无效标记。

代码：

#include <bitset>
#include <cstdio>
#include <iostream>
#define maxn 400010
using namespace std;
template <typename T>
void read(T &x) {
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + (ch ^ 48);
ch = getchar();
}
x *= f;
return;
}
int n, m;
struct E {
int to, nxt;
} edge[maxn << 1];
int head[maxn], top;
inline void insert(int u, int v) {
edge[++top] = (E) {v, head[u]};
head[u] = top;
}
int color[maxn], val[maxn], dfn[maxn], size[maxn], tmr;
void dfs(int u, int pre) {
dfn[u] = ++tmr;
size[u] = 1;
val[tmr] = color[u];
for (int i = head[u]; i; i = edge[i].nxt) {
int v = edge[i].to;
if (v != pre) {
dfs(v, u);
size[u] += size[v];
}
}
}
namespace Segment_tree {
#define lc (nd<<1)
#define rc ((nd<<1)|1)
#define mid ((l + r) >> 1)
bitset<61> seg[maxn << 2];
bitset<61> tag[maxn << 2];
inline void put_tag(int nd, bitset<61> op) {
if (op.count()) //关键，以及第一个调炸的点
seg[nd] = op,
tag[nd] = op;
}
inline void push_down(int nd) {
put_tag(lc, tag[nd]);
put_tag(rc, tag[nd]);
tag[nd].reset();//第二个调炸的点：忘记清除标记
}
inline void update(int nd) {
seg[nd] = seg[lc] | seg[rc];
}
void build(int nd, int l, int r) {
if (l == r) {
seg[nd].set(val[l], 1);
return;
}
build(lc, l, mid);
build(rc, mid + 1, r);
update(nd);
}
void modify(int nd, int l, int r, int ql, int qr, bitset<61> op) {
if (l >= ql && r <= qr) {
put_tag(nd, op);
return;
} else if (l > qr || r < ql)
return;
push_down(nd);
modify(lc, l, mid, ql, qr, op);
modify(rc, mid + 1, r, ql, qr, op);
update(nd);
}
bitset<61> query(int nd, int l, int r, int ql, int qr) {
if (l >= ql && r <= qr)
return seg[nd];
if (l > qr || r < ql) {
bitset<61> t;
return t;
}
push_down(nd);
return query(lc, l, mid, ql, qr) | query(rc, mid + 1, r, ql, qr);
}
} using namespace Segment_tree;
int main() {
read(n), read(m);
for (int i = 1; i <= n; ++i)
read(color[i]);
int u, v, t, k;
for (int i = 1; i < n; ++i) {
read(u), read(v);
insert(u, v), insert(v, u);
}
dfs(1, 0);
build(1, 1, n);
bitset<61> op;
for (int i = 1; i <= m; ++i) {
read(t), read(v);
if (t == 1) {
read(k);
op.reset();
op.set(k, 1);
modify(1, 1, n, dfn[v], dfn[v] + size[v] - 1, op);
} else {
op = query(1, 1, n, dfn[v], dfn[v] + size[v] - 1);
printf("%d\n", op.count());
}
}
return 0;
}

巴特西

【CF620E】New Year Tree

题意翻译

最新文章

热门文章