DFS 序把子树化为区间;用 n 位颜色位集表示一段区间的颜色集,位置分块后由线段树维护块位集的并,询问只需 O(log nb) 次或加两侧暴力扫描。
OJ: roj
题目 ID: 1760
难度:提高+/省选-
标签:数据结构分块位运算线段树DFS 序python
创建: 2026-10-07 23:45
更新: 2026-10-07 23:45
形式化题目
给定一棵
:设子树 的顶点集合为 ,求 , 即这些顶点里颜色落在 的不同颜色个数; :把 改成 。
正解
思路
第一步:把子树变成区间。 对树做一次从根出发的 DFS,记
第二步:颜色只有
区间内出现过的、颜色在
的种数 = 该区间颜色位集 与掩码 做与之后 bit_count。
关键在于:两个颜色位集的并就是一次按位或,因此"多段颜色的合并"可以交给任意一种
支持区间并的数据结构来做,而"种数"不需要在合并过程中维护——最后数一次二进制里的
第三步:位置分块 + 线段树。 把 DFS 序按每
其中 bit_count 输出。
第四步:修改。 改一个顶点的颜色,只会影响它所在的那一个位置块的位集
- 直接重建:重新扫这个块的
个位置得到新的 ,再沿叶到根重算 个祖先, 单次代价 , 时也就是一两千次操作; - 补一张计数表
CNT[(c, b)]:只有"旧颜色计数减到"或"新颜色计数原本是 "时 块位集才真的变化,其余情况可以完全不碰线段树。
两份代码各取一条:C++ 取直接重建(Counter 一行建好,且
第五步:强制在线的两个细节。 异或解码后的 1 1 2 7 而
说明:本题素材源带数据生成脚本(
data.py),仓库内data/是自造的, 题面也可能来自网络重建,出题意图与官方原题可能存在偏差。上述做法按题面推导, 已在data/全部 10 组点上与参考答案逐字节一致。
代码
两份代码共用同一套骨架(DFS 序 → 位置分块 → 块位集线段树),只有两个常数不同:
C++ 取
C++ 版:位集写成 unsigned long long seg[2 * MAXP][MAXNW],每 64 个颜色一个字,
合并是逐字或、计数是 __builtin_popcountll;询问时只对颜色区间 memset 与或,不去白扫无关的字。
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-10-07 22:55
* update_at: 2026-10-07 23:45
*/
// ROJ 1760《树上数颜色》
//
// 题意:n 个点的树(根为 1),点 i 的颜色 c_i ∈ [1, n],操作分两种:
// 1 u l r : 询问子树 u 中,颜色落在 [l, r] 的颜色种数;
// 2 u c : 把点 u 的颜色改成 c;
// t = 1 时,除操作类型外的每个数都要异或上一次询问的答案 lastans。
//
// 做法:DFS 序把「子树」变成「连续区间」,问题化为:区间内出现过的、
// 颜色落在 [l, r] 的颜色种数。
// * 颜色只有 n 种,用「哪些颜色出现过」的 n 位位集表示一段区间;
// 两个位集的并 = 一次按位或,种数 = 位集与颜色区间掩码相与后的 popcount。
// * 位置(DFS 序)每 BLK 个一块,块 b 的位集记作 M_b,用线段树维护 M_b 的并
// (节点存两个儿子位集的或)。
// * 询问 [L, R] x [l, r] = 头部残缺 + 中间若干完整块 + 尾部残缺:
// 完整块在 O(log nb) 次或运算内并成一个位集,两侧残缺部分逐位置把颜色或进去,
// 最后只在颜色区间 [l, r] 对应的字上做 popcount。
// * 修改:只需重建它所在那一个位置块的位集(扫该块 BLK 个位置),再沿叶到根
// 重算 O(log nb) 个祖先。
// 复杂度:询问 O((r-l)/64 + log nb),修改 O(BLK + log nb · n/64);nb = n/BLK。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN = 100005; // 点数上界
const int BLK = 1000; // 位置(DFS 序)分块大小
const int MAXNB = MAXN / BLK + 2; // 位置块数上界
const int MAXNW = MAXN / 64 + 2; // 一个位集占的 64 位字数(颜色 1..n 共 n 位)
const int MAXP = 128; // 线段树叶子偏移,2 的幂且 ≥ MAXNB
ull seg[2 * MAXP][MAXNW]; // 颜色位集线段树:叶在 seg[P..P+nb-1]
ull acc[MAXNW]; // 询问时的临时并集,只用到颜色区间覆盖的那些字
int n, q, t; // 点数、操作数、是否强制在线
int nb, P, nw; // 位置块数、叶子偏移、位集字数
struct Edge { int to, next; }; // 边表(链式前向星)
Edge eg[2 * MAXN];
int head[MAXN];
int ecnt;
int color[MAXN]; // 每个点当前的颜色
int par[MAXN]; // DFS 中的父节点,用于判重
int tin[MAXN], tout[MAXN], euler[MAXN]; // 入时间、子树最大入时间、每个位置上的点
// ---------- 快读快写 ----------
static char rbuf[1 << 16];
static int rpos, rlen;
int gc() {
if (rpos == rlen) {
rlen = (int)fread(rbuf, 1, 1 << 16, stdin);
rpos = 0;
if (rlen <= 0) return -1;
}
return rbuf[rpos++];
}
int read_int() {
int c = gc(), x = 0;
while (c < '0' || c > '9') {
if (c < 0) return -1;
c = gc();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = gc();
}
return x;
}
static char wbuf[1 << 21];
static int wpos;
void out_int(int x) {
if (x == 0) {
wbuf[wpos++] = '0';
wbuf[wpos++] = '\n';
return;
}
char tmp[12];
int k = 0;
while (x > 0) {
tmp[k++] = '0' + x % 10;
x /= 10;
}
while (k > 0) wbuf[wpos++] = tmp[--k];
wbuf[wpos++] = '\n';
}
void add_edge(int u, int v) {
++ecnt;
eg[ecnt].to = v;
eg[ecnt].next = head[u];
head[u] = ecnt;
}
// 迭代 DFS:n 最大 1e5,一条链会爆递归栈,所以显式开栈。
void build_dfs() {
static int stk[MAXN]; // 栈里存点编号
static int it[MAXN]; // 每个点待访问的下一条边
int top = 0, timer = 0;
par[1] = 0;
stk[top++] = 1;
tin[1] = ++timer;
euler[timer] = 1;
it[1] = head[1];
while (top > 0) {
int u = stk[top - 1];
int e = it[u];
if (e == 0) { // 儿子都进过栈了,子树区间在此闭合
tout[u] = timer;
--top;
continue;
}
it[u] = eg[e].next;
int v = eg[e].to;
if (v == par[u]) continue; // 唯一的重复邻居就是父亲
par[v] = u;
tin[v] = ++timer;
euler[timer] = v;
it[v] = head[v];
stk[top++] = v;
}
}
// 重建位置块 b 的位集:扫它覆盖的 BLK 个位置
void build_leaf(int b) {
ull *row = seg[P + b];
memset(row, 0, (size_t)nw * sizeof(ull));
int last = (b + 1) * BLK;
if (last > n) last = n;
for (int p = b * BLK + 1; p <= last; ++p) {
int c = color[euler[p]];
row[c >> 6] |= 1ULL << (c & 63);
}
}
// 自叶向根重算祖先链
void repaint(int b) {
for (int i = (P + b) >> 1; i; i >>= 1) {
ull *cur = seg[i];
const ull *a = seg[2 * i], *c = seg[2 * i + 1];
for (int w = 0; w < nw; ++w) cur[w] = a[w] | c[w];
}
}
void build_seg() {
nb = (n + BLK - 1) / BLK;
P = 1;
while (P < nb) P <<= 1;
nw = (n >> 6) + 1;
for (int b = 0; b < nb; ++b) build_leaf(b);
for (int i = P - 1; i >= 1; --i) {
ull *cur = seg[i];
const ull *a = seg[2 * i], *c = seg[2 * i + 1];
for (int w = 0; w < nw; ++w) cur[w] = a[w] | c[w];
}
}
void modify(int u, int cnew) {
int old = color[u];
if (old == cnew) return;
color[u] = cnew;
int b = (tin[u] - 1) / BLK;
build_leaf(b); // 该块的位集可能整块都变了,直接重建
repaint(b);
}
int query(int L, int R, int l, int r) {
if (l < 1) l = 1; // 强制在线解码可能越界,夹回 [1, n]
if (r > n) r = n;
if (L > R || l > r) return 0;
int wl = l >> 6, wr = r >> 6; // 只有这些字上的位才可能计入答案
int fL = (L - 1 + BLK - 1) / BLK; // 第一个完整落在 [L, R] 里的位置块
int fR = R / BLK - 1; // 最后一个完整落进来的位置块
if (fL > fR) { // 没有完整块:整段落在相邻两个残缺块里
memset(acc + wl, 0, (size_t)(wr - wl + 1) * sizeof(ull));
} else {
memset(acc + wl, 0, (size_t)(wr - wl + 1) * sizeof(ull));
int i = fL + P, j = fR + P; // 线段树把完整块并成一个位集
while (i <= j) {
if (i & 1) {
const ull *a = seg[i];
for (int w = wl; w <= wr; ++w) acc[w] |= a[w];
++i;
}
if (!(j & 1)) {
const ull *a = seg[j];
for (int w = wl; w <= wr; ++w) acc[w] |= a[w];
--j;
}
i >>= 1;
j >>= 1;
}
}
// 头部残缺:第 fL-1 块的尾巴;尾部残缺:第 fR+1 块的脑袋
for (int p = L; p <= fL * BLK && p <= R; ++p) {
int c = color[euler[p]];
if (c >= l && c <= r) acc[c >> 6] |= 1ULL << (c & 63);
}
for (int p = (fR + 1) * BLK + 1; p <= R; ++p) {
if (p < L) p = L;
int c = color[euler[p]];
if (c >= l && c <= r) acc[c >> 6] |= 1ULL << (c & 63);
}
// 只在颜色区间 [l, r] 覆盖的字上数 1
int ans = 0;
if (wl == wr) {
ull m = (~0ULL << (l & 63)) & (~0ULL >> (63 - (r & 63)));
ans = __builtin_popcountll(acc[wl] & m);
} else {
ans = __builtin_popcountll(acc[wl] & (~0ULL << (l & 63)))
+ __builtin_popcountll(acc[wr] & (~0ULL >> (63 - (r & 63))));
for (int w = wl + 1; w < wr; ++w) ans += __builtin_popcountll(acc[w]);
}
return ans;
}
int main() {
n = read_int();
q = read_int();
t = read_int();
for (int i = 1; i <= n; ++i) color[i] = read_int();
for (int i = 1; i < n; ++i) {
int u = read_int(), v = read_int();
add_edge(u, v);
add_edge(v, u);
}
build_dfs();
build_seg();
int lastans = 0;
for (int i = 0; i < q; ++i) {
int op = read_int();
if (op == 1) {
int u = read_int(), l = read_int(), r = read_int();
if (t == 1) {
u ^= lastans;
l ^= lastans;
r ^= lastans;
}
lastans = query(tin[u], tout[u], l, r);
out_int(lastans);
} else {
int u = read_int(), c = read_int();
if (t == 1) {
u ^= lastans;
c ^= lastans;
}
modify(u, c);
}
}
fwrite(wbuf, 1, wpos, stdout);
return 0;
}Python 版:直接用任意精度整数当位集——第 list[int],"合并两段"与"数种数"退化成一次 | 与一次 .bit_count();
线段树叶子取满
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 23:10
# update_at: 2026-10-07 23:45
import sys
from collections import Counter
from collections.abc import Iterable
MAXC = 100000 # 颜色上界(题面 1 ≤ n ≤ 100000,颜色取值 1..n)
OCT = MAXC // 8 + 1 # 颜色位集的字节宽度:定宽才能反复用 int.from_bytes 拼同一个整数
BLK = 64 # 位置(DFS 序)分块大小:块内暴力扫,块间用线段树并
# 类型别名:这些复合类型在签名/声明里出现 ≥2 次,含义只在这里解释一遍
type Ints = list[int] # 一串整数:顶点编号 / 颜色表 / 位集线段树
type Bits = int # 颜色位集:二进制第 c 位为 1 表示颜色 c 出现过
type Edges = Ints # 边表:按 u, v 成对存放的 2(n-1) 个顶点编号
type Counts = dict[tuple[int, int], int] # (颜色, 位置块) -> 出现次数
# 模块级状态:build_index 里一次建好,query / modify 只读改,不再层层传参
N = 0 # 点数
P = 0 # 线段树叶子偏移(≥ 位置块数的 2 的幂)
TIN: Ints = [] # 顶点的 DFS 入时间(1 基)
TOUT: Ints = [] # 顶点子树内最大的入时间:子树 u 即位置区间 [TIN[u]-1, TOUT[u]-1]
ORDER: Ints = [] # ORDER[k] 是 DFS 序第 k 个位置(0 基)上的顶点
CLR: Ints = [] # 每个顶点当前的颜色
SEG: Ints = [] # 颜色位集线段树:叶在 SEG[P..P+nb-1],节点是两子节点位集的或
CNT: Counts = {} # 清位前必须先查它,否则会把还出现着的颜色误当成消失
def dfs_order(n: int, edges: Edges) -> tuple[Ints, Ints, Ints]:
"""按 DFS 序重排:返回 (入时间, 子树最大入时间, 每个位置上的顶点)。
显式开栈迭代深搜,避免 n = 1e5 的链把递归栈压爆;
已进过栈的儿子不会再进,所以唯一的重复邻居就是父亲。
"""
adj: list[list[int]] = [[] for _ in range(n + 1)]
for i in range(0, 2 * (n - 1), 2):
u, v = edges[i], edges[i + 1]
adj[u].append(v)
adj[v].append(u)
tin = [0] * (n + 1)
tout = [0] * (n + 1)
order = [0] * n
par = [0] * (n + 1) # 父节点,用来跳过回边
nxt = [0] * (n + 1) # 每个顶点下一条待访问的边(邻接表下标)
par[1] = -1
tin[1] = 1
order[0] = 1
timer = 1
stack = [1]
while stack:
u = stack[-1]
if nxt[u] == len(adj[u]): # 儿子都进过栈了,子树区间在此闭合
tout[u] = timer
stack.pop()
continue
v = adj[u][nxt[u]]
nxt[u] += 1
if v == par[u]:
continue
par[v] = u
timer += 1
tin[v] = timer
order[timer - 1] = v
stack.append(v)
return tin, tout, order
def bits_of(cols: Iterable[int]) -> Bits:
"""把一串颜色压成颜色位集(位编号的约定见 type Bits)。"""
buf = bytearray(OCT) # 定宽缓冲:所有位集字节数一致,才能直接按位或
for c in cols:
buf[c >> 3] |= 1 << (c & 7)
return int.from_bytes(buf, 'little')
def seg_tree(leaves: Ints) -> tuple[int, Ints]:
"""把每个位置块的颜色位集摆成线段树叶子:返回 (叶子偏移 P, 整棵树)。
叶子数补齐到 2 的幂 P,非叶节点是两个儿子位集的或,
于是任意一段完整块都能用 O(log) 个节点并出来。
"""
p = 1 << (len(leaves) - 1).bit_length()
seg = [0] * p + leaves + [0] * (p - len(leaves))
for i in range(p - 1, 0, -1):
seg[i] = seg[2 * i] | seg[2 * i + 1]
return p, seg
def build_index(n: int, clr: Ints, edges: Edges) -> None:
"""预处理好全套索引:DFS 序、每个位置块的位集、块位集线段树、(颜色, 块) 计数。"""
global N, P, TIN, TOUT, ORDER, CLR, CNT, SEG
N = n
CLR = clr
TIN, TOUT, ORDER = dfs_order(n, edges)
blocks = [ORDER[i:i + BLK] for i in range(0, n, BLK)] # 位置分块后的每一块
P, SEG = seg_tree([bits_of(CLR[v] for v in blk) for blk in blocks])
# 位集只能置位/清位,靠这张表才能判断某一位该不该清
CNT = Counter((CLR[v], k // BLK) for k, v in enumerate(ORDER))
def block_range(fL: int, fR: int) -> Bits:
"""位置块区间 [fL, fR] 的并集颜色位集:线段树自底向上取 O(log) 个节点。"""
seg = SEG # 绑到局部:循环里每层都要取一次全局名,绑一次就够了
i = fL + P
j = fR + P
acc = 0
while i <= j:
if i & 1: # i 是父节点的右儿子:它完全落在区间里,取走自己再右移
acc |= seg[i]
i += 1
if not j & 1: # j 是父节点的左儿子:同理取走
acc |= seg[j]
j -= 1
i >>= 1 # i-1、j+1 已经取走,剩下的是上一层的一对邻区间
j >>= 1
return acc
def repaint(b: int) -> None:
"""位置块 b 的位集变了:自叶向根重算它到根这条链上的 O(log) 个祖先。"""
seg = SEG
i = (P + b) >> 1
while i:
seg[i] = seg[2 * i] | seg[2 * i + 1]
i >>= 1
def query(u: int, l: int, r: int) -> int:
"""子树 u 里颜色落在 [l, r] 的颜色种数。
区间 = 头部残缺块 + 中间完整块(线段树并成一个位集)+ 尾部残缺块;
三部分并成同一个颜色位集,最后按 [l, r] 截取并数一次二进制里的 1。
"""
l = max(l, 1) # 强制在线解码可能把 l, r 送出界,夹回 [1, n]
r = min(r, N)
if l > r:
return 0
lo = TIN[u] - 1
hi = TOUT[u] - 1
span = ((1 << (r - l + 1)) - 1) << l # 只留颜色区间 [l, r] 的位,其余位置 0
fL = -(-lo // BLK) # 完整落在区间内的第一个位置块
fR = (hi + 1) // BLK - 1 # 完整落在区间内的最后一个位置块
if fL > fR: # 没有完整块:整段落在至多两个残缺块里
return (bits_of(CLR[v] for v in ORDER[lo:hi + 1]) & span).bit_count()
mask = block_range(fL, fR)
head_hi = fL * BLK - 1 # 头部残缺部分:第 fL-1 块的尾巴
if lo <= head_hi:
mask |= bits_of(CLR[v] for v in ORDER[lo:head_hi + 1])
tail_lo = (fR + 1) * BLK # 尾部残缺部分:第 fR+1 块的脑袋
if tail_lo <= hi:
mask |= bits_of(CLR[v] for v in ORDER[tail_lo:hi + 1])
return (mask & span).bit_count()
def modify(u: int, cnew: int) -> None:
"""把顶点 u 的颜色改成 cnew,同步块内计数、块位集与线段树。"""
old = CLR[u]
if old == cnew:
return
CLR[u] = cnew
b = (TIN[u] - 1) // BLK
leaf = P + b
gone = (old, b)
left = CNT[gone] - 1 # 旧颜色在这个块里还剩几次
CNT[gone] = left
born = (cnew, b)
seen = CNT.get(born, 0) # 新颜色在这个块里原有的出现次数
CNT[born] = seen + 1
# 位集只在「旧颜色清零」或「新颜色首现」时才变,两个改动合并成一次祖先重算
if left == 0:
SEG[leaf] &= ~(1 << old)
if seen == 0:
SEG[leaf] |= 1 << cnew
if left == 0 or seen == 0:
repaint(b)
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
n, q, t = next(data), next(data), next(data)
clr = [0] + [next(data) for _ in range(n)] # 顶点 1..n 的初始颜色,0 号位留空
edge_ints = 2 * (n - 1) # 边表占的整数个数
edges: Edges = [next(data) for _ in range(edge_ints)]
build_index(n, clr, edges)
out: Ints = []
lastans = 0
for _ in range(q):
op = next(data)
if op == 1:
u, l, r = next(data), next(data), next(data)
if t: # t=1:除操作类型外全都要异或
u, l, r = u ^ lastans, l ^ lastans, r ^ lastans
lastans = query(u, l, r)
out.append(str(lastans))
else:
u, c = next(data), next(data)
if t:
u, c = u ^ lastans, c ^ lastans
modify(u, c)
sys.stdout.write('\n'.join(out) + '\n')
if __name__ == "__main__":
solve()复杂度
记
- 预处理:DFS
;每个位置块的位集逐位置构造 ,线段树 次字或。 - 询问:线段树合并
次位集或(每次 字)+ 两侧残缺块各 次置位 - 一次
popcount,合计。
- 一次
- 修改:重置该位置块的位集
,再重算祖先链 ; 带计数表的 Python 版在块位集不变时直接跳过这两步。
空间:位集线段树
实测:在
Python 版还有一个值得记下的实现细节:第 10 号点(随机树 + 强制在线)实测峰值 RSS 约 int.from_bytes 现场拼出来的整数,宽度随该块颜色的最高位变化,
「取出子节点位集 → 或成新值 → 存回父节点」的往返会不断创建新的大整数对象,
CPython 的分配器会因此缓慢抬高驻留内存数。
它在 512 MB 限额内(通过),但这是 Python 版离 MLE 最近的一点:
若要拿 Python 版去冲更紧的内存限额,应该改成直接重建整块位集,
或用更小的块大小把单个位集的宽度压下来。
总结
- 子树即区间:任何"子树上的聚合"先做一次 DFS 序转区间,这是树上区间问题的通用第一步。
- 把"是否存在"压成位集:当对象种类数是
、而操作只问"有没有出现"时, 用 位整数表示集合能让"多段合并"退化成一次按位或;Python 的 int自带宽位运算, C++ 里则用一个unsigned long long数组手写。 - 布尔位集 + 计数表:位集只能置位/清位,不能减;凡是需要"删除"的场合都要补一张 出现次数表来决定这一位该不该清。
- 线段树的节点是位集时,一次询问只需要
次或,比"逐块扫"少一个 因子。 - 强制在线的区间参数必须夹取:异或解码后下标越界是常态,判题数据里就有这种点。