「Codeforces 620E」New Year Tree - DFS序 + 状态压缩 + 线段树

给定一棵以1为根的有根树,有n个点

每个节点初始有一个颜色c[i]。

有两种操作:

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

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

1 <= n, m <= 4e5

「Codeforces 620E」

因为只有子树操作,建图后按照DFS序建立线段树

将树上操作转换为序列操作

将颜色状态压缩成status,维护的时候xor就行了

最后统计答案使用__builtin_popcountll统计即可

话不多说看代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <stdio.h>
#include <algorithm>

typedef long long ll;

const int N = 4e5 + 5;
const int M = 8e5 + 5;

int n, m;
int cnt, dfn[N], begin[N], end[N];
int num_edge, head[N];
int col[N];

class Segment_Tree
{
#define ls (p << 1)
#define rs (p << 1 | 1)

private:
struct Node
{
ll status;
bool tag;
} t[N << 2];
void push_up(int p) { t[p].status = t[ls].status | t[rs].status; }
void push_down(int p)
{
if (t[p].tag)
{
t[p].tag = false;
t[ls].status = t[rs].status = t[p].status;
t[ls].tag = t[rs].tag = true;
}
}

public:
void build(int p, int l, int r)
{
if (l == r)
{
t[p].status = 1LL << col[dfn[l]];
return;
}
int mid = (l + r) >> 1;
build(ls, l, mid);
build(rs, mid + 1, r);
push_up(p);
}
void modify(int p, int l, int r, int x, int y, int val)
{
if (x <= l and r <= y)
{
t[p].status = 1LL << val;
t[p].tag = true;
return;
}
push_down(p);
int mid = (l + r) >> 1;
if (x <= mid)
modify(ls, l, mid, x, y, val);
if (mid < y)
modify(rs, mid + 1, r, x, y, val);
push_up(p);
}
ll query(int p, int l, int r, int x, int y)
{
if (x <= l and r <= y)
return t[p].status;
push_down(p);
int mid = (l + r) >> 1;
if (y <= mid)
return query(ls, l, mid, x, y);
if (mid < x)
return query(rs, mid + 1, r, x, y);
return query(ls, l, mid, x, y) | query(rs, mid + 1, r, x, y);
}
} T;

struct Edge
{
int next, to;
} edge[M];

void add_edge(int u, int v)
{
edge[++num_edge].next = head[u];
edge[num_edge].to = v;
head[u] = num_edge;
}

void dfs(int u, int fa)
{
dfn[++cnt] = u;
begin[u] = cnt;
for (int i = head[u]; i; i = edge[i].next)
{
int v = edge[i].to;
if (v != fa)
dfs(v, u);
}
end[u] = cnt;
}

int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &col[i]);
for (int i = 2; i <= n; i++)
{
int u, v;
scanf("%d%d", &u, &v);
add_edge(u, v), add_edge(v, u);
}
dfs(1, 0);
T.build(1, 1, n);
for (int i = 1; i <= m; i++)
{
int opt, v;
scanf("%d%d", &opt, &v);
if (opt == 1)
{
int c;
scanf("%d", &c);
T.modify(1, 1, n, begin[v], end[v], c);
}
else
{
ll ans = T.query(1, 1, n, begin[v], end[v]);
printf("%d\n", __builtin_popcountll(ans));
}
}
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×